- 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).
# Bubble Sort Demo
# Mr Street
def bubbleSort( aList ):
"""Performs the bubble sort on the list passed"""
leaveLoop = False
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
# 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.
""" 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]
|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).
""" Sorts the list by quick sort """
lesser = 
pivotList = 
greater = 
if len(aList) <= 1:
#choose first item for the pivot
pivot = aList
#compare to pivot
for i in aList:
if i < pivot:
#put items less than pivot into left hand list
elif i > pivot:
#put items greater than pivot into right hand list
#put itms same as pivot into pivotList
#quickSort the left hand side
lesser = quickSort(lesser)
#quickSort the right hand side
greater = quickSort(greater)
return lesser + pivotList + greater
a = [3,7,5,1,2,7,8,11,11,12,10,1,2,3,4,7,8]
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: