- Bubble Sort
- Insertion Sort
- Quick Sort
...followed by some videos of sorting algorithms in action.
The Bubble Sort
Not the most efficient algorithm in the computing world. Really inefficient algorithm- on average it is order n-squared, and at the very best case it is of order n time complexity, and at the worst case it is n-squared order of time complexity (ignoring the case where the list is already sorted, in which case it sorts in order n. In fact this is where the Bubble sort beats all other algorithms as the ability to detect that the list is sorted is built into the algorithm).
Python Implementation:
# Bubble Sort Demo
# Mr Street
# 2014-11-21
def bubbleSort( aList ):
"""Performs the bubble sort on the list passed"""
leaveLoop = False
while not(leaveLoop):
leaveLoop = True # assume we will have it sorted this time
#for each item in the list
for i in range(0, len(aList)-1):
#if this element is greater than the next item,
#then they should be swapped
if aList[i] > aList[i + 1]:
# python shortcut for swap
aList[i], aList[i+1] = aList[i+1], aList[i]
leaveLoop = False
print( aList)
# Test program
someList = [1, 3, 6, 7, 10, 5]
bubbleSort( someList )
 |
| Animated bubble sort example from Wikipedia. The Bubble sort gets its name because the sorted value 'bubbles' to the top of the list. |
The Insertion Sort
A very similar algorithm to the Bubble Sort, it is on average an order n squared time complexity. At the best case it is order (n) time complexity. The best case is when the list is almost in order, in which case it beats the quick sort. For this reason you should use the insertion sort to add items to an already sorted list, such as a contacts list.
Python Implementation:
def iSort(aList):
""" Insertion sort algorithm """
first = 0
last = len(aList)-1
for CurrentPointer in range(first+1, last+1):
CurrentValue = aList[CurrentPointer]
Pointer = CurrentPointer - 1
while aList[Pointer] > CurrentValue and Pointer >= 0:
aList[Pointer+1] = aList[Pointer]
Pointer -= 1
aList[Pointer+1] = CurrentValue
#A nearly sorted list, with one unsorted element to insert
a = [1, 4, 7, 8, 10, 5]
print("Unsorted")
print(a)
print("Sorted")
iSort(a)
print(a)
 |
| The insertion sort animation from Wikipedia. The algorithm works by find the correct place to insert an item. Unlike the bubble sort it only requires one pass through the list, although at the worst case each check will require n-1 comparisons. |
The Quick Sort
The quick sort algorithm works by 'divide and conquer': Choose a pivot point (the start of the list will do) and create two lists, one of unsorted items that are smaller than the pivot, and one of unsorted items that are greater than the pivot. Then perform the quicksort algorithm on each of the two unsorted lists.
The average case time complexity for the quick sort is therefore n log(n).
def quickSort(aList):
""" Sorts the list by quick sort """
lesser = []
pivotList = []
greater = []
if len(aList) <= 1:
return aList
else:
#choose first item for the pivot
pivot = aList[0]
#compare to pivot
for i in aList:
if i < pivot:
#put items less than pivot into left hand list
lesser.append(i)
elif i > pivot:
#put items greater than pivot into right hand list
greater.append(i)
else:
#put itms same as pivot into pivotList
pivotList.append(i)
#quickSort the left hand side
lesser = quickSort(lesser)
#quickSort the right hand side
greater = quickSort(greater)
return lesser + pivotList + greater
#Main program
print("Unsorted")
a = [3,7,5,1,2,7,8,11,11,12,10,1,2,3,4,7,8]
print(a)
print("Sorted")
print(quickSort(a))
Sorting videos
Fifteen algorithms in 6 minutes...
Sorting algorithms compared... place your bets now!
A very satisfying video showing sorting algorithms as colour wheel.
Other posts you might be interested in: