- 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 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: