ameerkat
12/7/2010 - 3:04 PM

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

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

``````# BunchO Sorting Algorithms
# Ameer Ayoub <ameer.ayoub@gmail.com>
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)
``````