Friday, May 8, 2009

Implementation of sort algorithms in python

I have found Wikipedia page about sorting algorithms. They are described in pseudo code, it is so easy to convert those in python code, so that I am hooked and can’t stop… :) Here is code, enjoy!
import random
import time

"""
Example of sorting algorithms implemented in python
GUID of this code sniped: 41ea3d8f-2330-4ddd-9e9d-ecd536ab4f4d 
Author: Darius Kucinskas (c) 2008-2009
Email: d[dot]kucinskas[eta]gmail[dot]com
Blog: http://blog-of-darius.blogspot.com/
License: GPL
"""

"""
simple bubble sort
"""
def bubble(l):
    sort_again = True
    while sort_again:
        sort_again = False

        i = 0
        size = len(l) - 1
        while i < size:
            if l[i] > l[i + 1]:
                swap(l, i, i + 1)
                sort_again = True
            i = i + 1

"""
insertion sort
"""
def insertion_sort(l):
    i = 0
    size = len(l) - 1
    while i < size:
        v = l[i]
        j = i - 1

        while j > 0 and l[j] > v:
            l[j + 1] = l[j]
            j = j - 1

        l[j + 1] = v
        i = i + 1

"""
shell sort
"""
def shell_sort(l):
    size = len(l)
    inc = int(size/2)

    while inc > 0:
        i = inc
        while i < size - 1:
            tmp = l[i]
            j = i
            while j >= inc and l[j - inc] > tmp:
                l[j] = l[j - inc]
                j = j - inc
            l[j] = tmp
            i = i + 1
        inc = int(inc/2.2)

"""
simple quicksort in python
"""
def quicksort1(l):
    if len(l) < 1:
        return l

    less = []
    greater = []

    pivot = l[len(l) / 2]
    l.remove(pivot)

    for i in l:
        if i < pivot:
            less.append(i)
        else:
            greater.append(i)

    return quicksort1(less) + [pivot] + quicksort1(greater)

def swap(l, a, b):
    tmp = l[a]
    l[a] = l[b]
    l[b] = tmp

if (__name__ == "__main__"):
    l = [i for i in range(10000)]
    print "sorted list"
    print l

    random.shuffle(l)
    print "unsorted original list"
    print l
    l2, l3, l4 = l[:], l[:], l[:]

    t1 = time.clock()
    bubble(l)
    t2 = time.clock()
    print "soted list l:"
    print l
    print "bubble sort time: %f " % (t2 - t1,)

    t1 = time.clock()
    insertion_sort(l2)
    t2 = time.clock()
    print "soted list l2:"
    print l2
    print "insertion sort time: %f " % (t2 - t1,)

    t1 = time.clock()
    shell_sort(l3)
    t2 = time.clock()
    print "soted list l3:"
    print l3
    print "shell sort time: %f " % (t2 - t1,)

    t1 = time.clock()
    lsorted = quicksort1(l4)
    t2 = time.clock()
    print "soted list l4:"
    print lsorted
    print "quick sort #1 time: %f " % (t2 - t1,)