Various sorts implemented in Python (Insertion, Bubble, Merge, Quick, Counting)

sorts.py

# BunchO Sorting Algorithms
# Ameer Ayoub <[email protected]>
# Last Modified 12/2/2010
import random

#
# Insertion Sort
#
def insertion_sort(l):
    """Given an input list, returns a sorted permutation of the list
    using insertion sort (run time upper bound : n^2)"""
    # English description:
    # Maintain a sorted subarray of the array from 0 to the current
    # number. Copy the current number and shift all the numbers of
    # the sorted subarray overwriting the copied number, once we get
    # to a location where the key is in the right position stop
    # shifting the numbers and insert the key.
    for i in range(1, len(l)):
        # Copy the key value so we can overwrite it when shifting
        key = l[i]
        j = i - 1
        while j >= 0 and l[j] > key:
            # Shift over all the entries greater than key
            l[j+1] = l[j]
            j = j - 1
        # Now copy the key into the appropriate spot left by
        # shifting all the greater values over
        l[j+1] = key
    return l

#
# Bubble Sort
#
def bubble_sort(l):
    """Given an input list, returns a sorted permutation of the list
    using bubble sort (run time upper bound : n^2)"""
    swapped_flag = True
    while swapped_flag:
        swapped_flag = False
        for i in range(1, len(l)-1):
            if l[i] > l[i+1]:
                # pythony swap
                l[i], l[i+1] = l[i+1], l[i]
                swapped_flag = True
    return l

def optimized_bubble_sort(l):
    for i in range(0, len(l)):
        for j in range(i+1, len(l))[::-1]:
            if l[j-1] > l[j]:
                l[j-1], l[j] = l[j], l[j-1]
    return l

#
# Merge Sort
#
def merge(l1, l2):
    m = []
    i = 0
    j = 0
    while i < len(l1) or j < len(l2):
        if i < len(l1) and l1[i] < l2[j]:
            m.append(l1[i])
            i = i+1
        else:
            m.append(l2[j])
            j = j+1
    return m

def merge_sort(l):
    if len(l) <= 1:
        return l
    mid = len(l)/2
    return merge(merge_sort(l[:mid]), merge_sort(l[mid:]))

#
# QuickSort
#

# Nonrandomized Pivot
def partition(l, p, q):
    x = l[p]
    i = p
    for j in range(p+1, q):
        if l[j] <= x:
            i += 1
            l[i], l[j] = l[j], l[i]
            print "Swapping: ", l[i], " and ", l[j]
    l[p], l[i] = l[i], l[p]
    return l, i

#Randomized Pivot
def partition_r(l, p, q):
    random.seed()
    pivot = random.randint(p, q-1)
    return partition(l, pivot, q)

def quicksort_r(l, p, q):
    if p < q:
        l, r = partition_r(l, p, q)
        quicksort(l, p, r-1)
        quicksort(l, r+1, q)
    return l

def quicksort(l, p, q):
    if p < q:
        l, r = partition(l, p, q)
        quicksort(l, p, r-1)
        quicksort(l, r+1, q)
    return l

#
# Counting Sort
#
def counting_sort(l):
    j = min(l)
    k = max(l)
    c = {}
    b = []
    for t in range(j, k+1):
        c[t] = 0
    for t2 in range(0, len(l)):
        b.append(0)
    for item in l:
        c[item] += 1
    # Calculate the prefix sums
    for t3 in range(j+1, k+1):
        c[t3] += c[t3-1]
    for t4 in range(0, len(l))[::-1]:
        b[c[l[t4]]-1] = l[t4]
        c[l[t4]] = c[l[j]]-1
    return b


if __name__ == "__main__":
    l = [5, 1, 21, 32, 64, 23, 17]
    print "Insertion sort: \t", insertion_sort(l)
    print "Bubble sort: \t\t", bubble_sort(l)
    print "Optimized bubble sort: \t", optimized_bubble_sort(l)
    print "Merge sort: \t\t", merge_sort(l)
    print "Quicksort: \t\t", quicksort(l, 0, len(l)-1)
    print "Randomized Quicksort: \t", quicksort_r(l, 0, len(l)-1)
    print "Counting sort: \t\t", counting_sort(l)