Bubble Sort

excerpt: How does bubblesort work? What is the time complexity? When can we use bubblesort? tags: swap linear-scan value-comparison adjacent-pair-comparison

Bubblesort uses the fact that in an unsorted array, there must be two adjacent elements that are out of order. The algorithm scans from right to left repeatedly, swapping items that are out of order, until there are no out of order items.

Bubblesort

The steps in the bubblesort algorithm are:

Define a bubblesort method that takes the array as the parameter.
Define a not_sorted flag and initialize its value to true.
Loop while not_sorted flag is true:
- Assume we will not find a pair to swap. Initialize the not_sorted to false.
- Search the array for adjacent items that are out of order.
  - Iterate from 0 to length of array - 1 Check if items i and i - 1 are out of order. If array[i] < array[i - 1], swap them Flip the not_sorted flag to true. Because the array is sorting is not done yet.

The not_sorted boolean variable keeps track of whether swap was made in the most recent pass through the array. As long as not_sorted is true, the while loop continues to look for adjacent pairs of items that are out of order and swaps them.

The diagram shows an example. The array is mostly sorted. The first pass through the array find that the 6/3 pair is out of order (6 should come after 3), so it swaps 6 and 3 to get the second arrangement of values.

The second pass through the array finds that the 5/3 pair is out of order, so it swaps 5 and 3 to get the third arrangement of values. The third pass through the array finds that the 4/3 pair is out of order, so it swaps 4 and 3, giving the arrangement shown in the fourth diagram. The algorithm performs one final pass, finds no pairs that are out of order and ends.

The item 3 slowly bubbles up to its correct position. This gives the bubblesort algorithm its name. During each pass through the array, at least one item reaches its final position. In this example, item 6 reaches its final destination during the first pass, item 5 reaches its final destination during the second pass. Items 3 and 4 reach their final destinations during the third pass.

If the array holds N items and at least one item reaches its final position during each pass through the array, the algorithm can perform, at most, N passes. If the array is initially sorted in reverse order, N passes is required. Each pass takes N steps, so the total run time is O(N2).

Bubblesort is fairly slow but may provide acceptable performance for small lists of about 1000 items or so.

Recursive Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def sort(array, swaps, size)
  if swaps == 0
    return array
  else
    swaps = 0

    for i in (0..size-2) do
      if array[i] > array[i+1]
        array[i], array[i+1] = array[i+1], array[i]
        p array
        swaps = 1
      end
    end

    return sort(array, swaps, size-1)  
  end
end

sort([4,2,7,1,3], 1, 5)

Iterative Implementation

The solution for move maximum problem can be extended by repeating the moving of maximum element to the end of the array for all the elements in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def bubble_sort(a)
  n = a.size
  
  n.times do
    for i in (1..n-1)
      if a[i-1] > a[i]
        a[i-1], a[i] = a[i], a[i-1]
      end
    end
  end
end

a = [4,3,2,9,7,0]
bubble_sort(a)

p a

This naive implementation will run n times even if the numbers are already sorted. This can be improved by using a flag to check whether there was any swap or not. If there was no swap, the method can terminate.

Nested for loops can be used but the outer for loop index is not used in the code within the outer loop, so it does not make sense to use a outer for loop.