The Bubble Sort Algorithm

A bubble sort works as follows. For every item in the list, starting at the first:

• If the current item is greater than the item to the immediate right then swap the two numbers around
• Move to the next item in the list and repeat. If this item is greater than the next, then swap the two items around
• When the end of the list is reached, start again.
• If next pass through the list results in no swaps, then the list is sorted

Consider the list of numbers:

10, 4, 99, 7

We start the sort at the first number which is is 10:

The number 10 is greater than the number 4 to the immediate right and so they are swapped around.

Now we move to the second number in the list which is now 10. We find that 10 is less than 99 and so they stay in the same positions:

Now we move to the 3rd number in the list which is 99. We find that 99 is greater than the number to the immediate right which is 7 and so the items are swapped over:

Now we start again at the first item, which is 4. The number to the immediate right is 10 which is greater than 4 and so nothing happens:

Moving to the next item in the list which is 10. We find 10 is greater than 7 and so they are swapped over:

Lastly we check the 3rd item in the list against the 4th which compares 10 against 99. We find 10 is not greater than 99 and so they stay in the same positions:

Now we start again at the beginning and run through the list for a third time from start to finish. We cannot find that any swaps are necessary and so the list must be in sorted order and we finish.

The bubble sort is considered one of the slower sorting algorithms and is rarely used in practice because it is often the case that the entire list of numbers needs to be inspected several times before the list is sorted. Faster approaches include the insertion sort and merge sort, which don’t need to do this.

We can make an improvement to the bubble sort by noticing that on the first pass through the numbers, the largest number in the set is always pushed to the end. On the 2nd pass through the numbers, the 2nd largest number is always pushed into the 2nd to last position. On the 3rd pass, the 3rd largest is always pushed into the 3rd to last position and so on.

This means that on the 2nd pass through the number list, we don’t need to bother looking at the last number because we know it must already be in the correct sorted position i.e. at the end of the list and a swap will never be required. On the 3rd pass through the numbers we don’t need to bother looking at the 2nd to last number because again it must be in the correct sorted position and will never need swapping and so on.

However, even with this improvement, the bubble sort is still not the fastest method of sorting numbers.

Implementation of a Bubble Sort in Python

def bubble_sort_algorithm( list_of_values ):
	
	while True:
	
		did_swap = False
		
		#Loop from the start of the list to one number prior to the end
		for i in range( 0, len( list_of_values ) - 1 ):
			
			#Compare the number we are at with the number to the immediate right
			if list_of_values[i] > list_of_values[i+1]:
			
				#If the number to right it greater then swap it with the current number
				temp = list_of_values[i]
				list_of_values[i] = list_of_values[i+1]
				list_of_values[i+1] = temp
				
				#Make a note that we swapped over numbers on this pass
				did_swap = True
				
		#Continue looping through the list of values until such time as we do not swap any around 		
		#When we have fully completed a pass through the numbers without swapping any then the list is sorted
		if not did_swap:
			break


if __name__ == "__main__":
	
	list_to_be_sorted = [ 10, 4, 99, 7 ]
	
	bubble_sort_algorithm( list_to_be_sorted )
	
	print( list_to_be_sorted )

An Implementation of the Improved Bubble Sort

This version of the bubble sort takes into account the observation about avoiding looking at the end of the list when we can be certain the numbers are sorted.

def optimised_bubble_sort_algorithm( list_of_values ):

	length_to_inspect = len( list_of_values )
	
	while True:
	
		did_swap = False
		
		#Loop from the start of the list to one number prior to the end
		#We look at one fewer numbers with each pass through the list
		for i in range( 0, length_to_inspect - 1 ):
			
			#Compare the number we are at with the number to the immediate right
			if list_of_values[i] > list_of_values[i+1]:
			
				#If the number to right it greater then swap it with the current number
				temp = list_of_values[i]
				list_of_values[i] = list_of_values[i+1]
				list_of_values[i+1] = temp
				
				#Make a note that we swapped over numbers on this pass
				did_swap = True
		
		length_to_inspect -=1
				
		#Continue looping through the list of values until such time as we do not swap any around 		
		#When we have fully completed a pass through the numbers without swapping any then the list is sorted
		if not did_swap:
			break


if __name__ == "__main__":
	
	list_to_be_sorted = [ 10, 4, 99, 7 ]
	
	optimised_bubble_sort_algorithm( list_to_be_sorted )
	
	print( list_to_be_sorted )