Bubble sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
A bubble sort illustrated

Bubble sort is a simple sorting algorithm. It is simple to understand, so it is used as a training algorithm. It is not used in the real world, since it is not very efficient.

Algorithm[change | change source]

To sort a list of numbers, the bubble sort goes through the list and compares every number to the next one. If those two numbers are in the wrong order, it will swap them. It will repeat this process, going back to the beginning every time it finishes, until the list is fully sorted. Any list of numbers with the length n can be sorted in under n-1 rounds.

First pass:
(4, 3, 1, 2) → (3, 4, 1, 2)
(3, 4, 1, 2) → (3, 1, 4, 2)
(3, 1, 4, 2) → (3, 1, 2, 4)

Second pass:
(3, 1, 2, 4) → (1, 3, 2, 4)
(1, 3, 2, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)

Third pass:
(1, 2, 3, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)

Implementation[change | change source]

 1 def bubble_sort():
 2 	# Set the variable of sorted
 3 	sorted = False
 4 
 5 	# While we have swapped a variable...
 6 	while not sorted:
 7 
 8 		# Assume it's sorted
 9 		sorted = True
10 
11 		# For every element in the array except the last...
12 		for i in range(len(array) - 1):
13 
14 			# If the element is larger than the one to the right of it...
15 			if array[i] > array[i + 1]:
16 
17 				# Swap the two elements
18 				array[i], array[i + 1] = array[i + 1], array[i]
19 
20 				# And mark that we have swapped something this pass
21 				sorted = False
22 
23 	# Return sorted array
24 	return array

This is pass optimized implementation of the algorithm. Obviously, there is no necessity to do passes if array was sorted or became sorted after one of the passes. So in this implementation there is a flag swapped which signalize whether was swapped elements in the current pass or not. If not then cycle is ended. In the best case, then array is sorted already, complexity of this implementation is O(n). In the worst case, then array sorted by descending, complexity is O(n2).

Other websites[change | change source]