This post includes Python based implementation of some of the classic basic sorting algorithms. Although Python already includes the excellent Timsort algorithm implementation, this was done more as an academic exercise to not forget the basic principles of sorting.
Each sorting algorithm is implemented as a Python function, which will sort the list in-place. I used the following piece of code to test all the algorithms.
import random
random_items = [random.randint(-50, 100) for c in range(32)]
print 'Before: ', random_items
insertion_sort(random_items)
print 'After : ', random_items
http://en.wikipedia.org/wiki/Bubble_sort
Bubble sort is one of the most basic sorting algorithm that is the simplest to understand. It’s basic idea is to bubble up the largest(or smallest), then the 2nd largest and the the 3rd and so on to the end of the list. Each bubble up takes a full sweep through the list.
def bubble_sort(items):
""" Implementation of bubble sort """
for i in range(len(items)):
for j in range(len(items)-1-i):
if items[j] > items[j+1]:
items[j], items[j+1] = items[j+1], items[j] # Swap!
http://en.wikipedia.org/wiki/Insertion_sort
Insertion sort works by taking elements from the unsorted list and inserting them at the right place in a new sorted list. The sorted list is empty in the beginning. Since the total number of elements in the new and old list stays the same, we can use the same list to represent the sorted and the unsorted sections.
def insertion_sort(items):
""" Implementation of insertion sort """
for i in range(1, len(items)):
j = i
while j > 0 and items[j] < items[j-1]:
items[j], items[j-1] = items[j-1], items[j]
j -= 1
http://en.wikipedia.org/wiki/Merge_sort
Merge sort works by subdividing the the list into two sub-lists, sorting them using Merge sort and then merging them back up. As the recursive call is made to subdivide each list into a sublist, they will eventually reach the size of 1, which is technically a sorted list.
def merge_sort(items):
""" Implementation of mergesort """
if len(items) > 1:
mid = len(items) / 2 # Determine the midpoint and split
left = items[0:mid]
right = items[mid:]
merge_sort(left) # Sort left list in-place
merge_sort(right) # Sort right list in-place
l, r = 0, 0
for i in range(len(items)): # Merging the left and right list
lval = left[l] if l < len(left) else None
rval = right[r] if r < len(right) else None
if (lval and rval and lval < rval) or rval is None:
items[i] = lval
l += 1
elif (lval and rval and lval >= rval) or lval is None:
items[i] = rval
r += 1
else:
raise Exception('Could not merge, sub arrays sizes do not match the main array')
http://en.wikipedia.org/wiki/Quicksort
Quick sort works by first selecting a pivot element from the list. It then creates two lists, one containing elements less than the pivot and the other containing elements higher than the pivot. It then sorts the two lists and join them with the pivot in between. Just like the Merge sort, when the lists are subdivided to lists of size 1, they are considered as already sorted.
def quick_sort(items):
""" Implementation of quick sort """
if len(items) > 1:
pivot_index = len(items) / 2
smaller_items = []
larger_items = []
for i, val in enumerate(items):
if i != pivot_index:
if val < items[pivot_index]:
smaller_items.append(val)
else:
larger_items.append(val)
quick_sort(smaller_items)
quick_sort(larger_items)
items[:] = smaller_items + [items[pivot_index]] + larger_items
http://en.wikipedia.org/wiki/Heapsort
This implementation uses the built in heap data structures in Python. To truly understand haepsort, one must implement the heapify() function themselves. This is certainly one obvious area of improvement in this implementation.
import heapq
def heap_sort(items):
""" Implementation of heap sort """
heapq.heapify(items)
items[:] = [heapq.heappop(items) for i in range(len(items))]