3.9.1 Bubble Sort

Knowledge Base > Algorithm > Sorting

Overview

The first sorting method probably many people learn in the first time is Bubble sort, because it is straightforward and easy to learn. The simple idea is keep passing through the list, swapping the next element that is out of order, until the list is sorted. However, this algorithm is very inefficient, and rarely used in practice, exception in computer science education. This method normally performs O(n²) in both average case and worst case.

Algorithm

Pseudocode

Bubble-Sort(A)

1 for i ← 1 to length[A] 2 do for j ← length[A] downto i + 1 3       do if A[j] < A[j - 1] 4                then swap A[j] ↔ A[j - 1]

Suppose we have an list that we are going to sort in ascending order, that is, smallest element at the left end and largest element at the right end. We first scan from right to left, compare it with its adjacent element to the left , swap them if they are in the wrong order, and advance to the next index. Eventually the smallest element would be pushed it into the left end of the list. Then, in the second round, the second smallest element would be put in the second left-most position. Repeat this until no swaps have occurred on the last pass. Please note we are not finding the smallest element in each round, but to eventually sort the encountered pair in order.

Loop Invariant for Inner Loop
Statement
Before the start of the j^th iteration, A[j] stores the smallest value among A[j…n].
Initialization
Before the 1^st iteration, j = n, so A[j] stores the smallest value of A[n…n], and decide A[n] and A[n = 1].
Maintenance
Before the j^th iteration, A[j] stores the smallest element among A[j…n]. After running through line 3 and 4, A[j - 1] contains the smallest element among A[j - 1…n].
Termination
When exiting the loop, j = i, A[i] = A[j] stores the smallest value while among A[i…n], also A[j…n].

Loop Invariant for Outer Loop
Statement
Before the start of the i^th iteration, A[1…i- 1] stores the 1^st (i-1) smallest elements in A in sorted order.
Initialization
Before the 1^st iteration, i = 1, A[1…0] is an empty array, so is trivially sorted.
Maintenance
Before the i^th iteration, A[1…i - 1] has 1^st (i-1) smallest elements in A in sorted order. After running line 2-4, A[1…i] has 1^st (i) smallest elements in A in sorted order.
Termination
When exiting the loop, i = n + 1, A[1…n] stores the 1^st (n) elements in sorted order, which A[1…n] is the whole array.

Thus, prove the correctness of Bubble-Sort.

Time Complexity

Suppose we have an list with n elements, and each element perform n - 1 comparisons with elements to its left, and swap, if necessary. If the list is already sorted, that is, the best case, only one iteration is performed O(1); otherwise, n elements needs to perform at most n - 1 swap operations in each pass. Thus, this method produce a O(n²) running time and number of swaps in both average case and worst case.

Space Complexity

This is an in-place algorithm, which means no more than constant space is required to perform the operation. Thus, the space complexity is O(1).

Stability

After comparison, this method does not swap a pair of element, unless they do not pass the relational test < or > test, depending on the type of order you wish to sort. This preserve the same order of occurrence for two duplicated elements, after the list is sorted. However, if the relational test include equality relation, this method is no longer stable.

Source Code

• Bubble Sort (C)
  
  
  
• Bubble Sort (Scheme)