Saturday, November 17, 2012

Sorting in Python

#-------------------------------------------------------------------------------
# Name:        Methods of sorting
# Purpose:     implements the sortings mentioned by Robert Sedgewick and
#               Kevin Wayne, Algorithms 4ed
#
#-------------------------------------------------------------------------------

def selection_sort(a):
    for i in range(len(a)):
        min = i
        for j in range(i+1, len(a)):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]

def insertion_sort(a):
    for i in range(len(a)):
        j = i
        while j > 0:
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
            j -= 1

def shell_sort(a):
    h = 1
    while h <= len(a)/3:
        h = 3*h+ 1 # in the test use 4 as increment sequence
    while h >= 1:
        for i in range(len(a)):
            j = i
            while j >= h and a[j] < a[j-h]:
                a[j], a[j-h] = a[j-h], a[j]
                j -= h
        h /= 3

def merge_sort(x):
    result = []
    if len(x) < 2:
        return x
    mid = int(len(x)/2)
    y = merge_sort(x[:mid])
    z = merge_sort(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

def quick_sort(a):
     if len(a) <= 1:
          return a
     else:
          return quick_sort([x for x in a[1:] if x < a[0]]) + [a[0]] \
                + quick_sort([x for x in a[1:] if x >= a[0]])

if __name__ == '__main__':
    a = [7, 10, 1, 1, 3, 4, 5, 9, 2, 8]
    b = {}
    for i in range(1, 6):
        b['test'+str(i)] = a[:]
    # Test the three simple sortings
    insertion_sort(b['test1'])  #1
    selection_sort(b['test2'])  #2
    shell_sort(b['test3'])      #3
    print b
    # Test the sortings that requires recursion
    print merge_sort(b['test4'])        #4
    print quick_sort(b['test5'])        #5
    # Timsort that is native in Python
    a.sort()                            #6
    print a

Good math, bad engineering

As a formal statistician and a current engineer, I feel that a successful engineering project may require both the mathematician’s abilit...