Sorting Algorithms

Bubble Sort

In computer science courses, bubble sort is often the first introduction to sorting, so we start here. The implementation:

bubbleSort(array):
	for (int i = array.length,  i > 0,  i--):
		for (int j = 0,  j < i,  j++):
			if (array[j+1] < array[j]):
				swap(array[j+1], array[j])
	return array

Here's a visual, sorting the array [-1,2,9,7,8,4].

The idea behind bubble sort: We move through the array, comparing the current element at index ${i}$ (${n_i}$) against the element at index ${i+1}$ (${n_{i+1}.}$) If ${n_{i+1} > {n_{i}},}$ we swap the two elements. In the table, the pass column indicates one complete loop through the array. Notice that we loop through the array 7 times. This follows from the fact that the algorithm just swaps adjacent elements. The algorithm has no data about whether the entire array is sorted. All it does is loop, compare, compare, compare, ..., loop, compare, compare, compare, ..., swap if need be.

This is inefficient. After the first pass, the array is completely sorted. We're wasting both time and processor resources by continuing to loop and compare. We can fix this somewhat with the following change, a tiny optimization that requires additional memory:

bubbleSort(array):
	let noSwap
	for (int i = array.length,  i > 0,  i--):
		noSwap = true
		for (int j = 0,  j < i,  j++):
			if (array[j+1] < array[j]):
				swap(array[j+1], array[j])
				noSwap = false
			if (noSwap) break
	return array

By introducing a noSwap variable, we've cut down on the amount of steps from 28 to 19. The noSwap variable effectively tells the algorithm not to continue in the inner loop if no swap was performed. This gets straight to our previous annoyance: If no swap was performed, we know that the elements are sorted, so there's no need to continue looping.

Selection Sort

Closely related to bubble sort is selection sort. The implementation: