Bubble Sort

Tags

algorithm

Is a sorting algorithm which bubbles values to their correct position in the array. At the end of each iteration at least one new value is guaranteed to be in its correct position in the sorted array.

Formulation

n = len(arr) - 1
for i in range(n):
    swap = 0
    for j in range(n - i):
	if arr[j] > arr[j + 1]:
	    swap(arr, j, j + 1)
	    swap = 1

    if swap == 0:
	break

You can see the bubble sort algorithm in alg:bubble-sort. To explain the algorithm lets first consider the first iteration of the inner-loop of \( j \). In this loop we start at the beginning of the array and compare the first element with the element next to it. If they are out of order then we swap them, if they are in order then we leave them alone. Either way we then move on and compare the \nth{2} and \nth{3} elements. This process essentially bubble the largest value of the array to the end of it. If for example the largest value is right at the beginning of the array, it's swapped with the \nth{2} value, and then \nth{3} and so on and so forth until it's at the end of the array. If the largest value was at some other position \( m \) then the largest value in the sub-range \( [0, m-1] \) is bubbled to \( m-1 \) and then \( m \) is bubbled to the end. The core idea is at the end of the inner loop the right most element is in its correct position in the final array because by definition it was larger than all the other elements that were checked. We then reduce the length of the array by 1 (the unsorted range lies between \( [0, n-1] \) now because \( a[n] \) is correct) and repeat the same process another time. This time the second largest value is bubbled to the correct \( n-\nth{1} \) position. This repeats for the entire length of the array until everything is in its correct position.

This implementation also has an extra check for performance (swap) which records whether at least one element of the array was swapped in the inner loop. If it wasn't than all the elements in that range were in-order and by definition the array is sorted. This means no further iterations need to be performed.