Sorting Algorithms in #python

Should it be of use to students of Computing, here are three sorting algorithms in Python:

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