'''sorter.py -- implementations of several sorting algorithms

Jeff Ondich, 27 Feb 2007

This module contains simple implementations of several well-known
sorting algorithms, plus some utility code to help you investigate
the time complexity properties of these algorithms.

I have inserted comparison-counting code into bubbleSort to give you
the idea of how to do the comparison counting you need to do for
the exam.  It's important to understand why "comparisonCount += 1" 
precedes the "if" statement rather than being inside the "if" body.

I placed the sorting functions inside a class to give all of them
easy access to a "comparisonCount" variable.

Run "python sorter.py" to get a usage statement describing how to run
this program to test the various algorithms.
'''

import random
import time
import sys

class Sorter:
    def __init__(self):
        self.comparisonCount = 0

    def shuffle(self, theList):
        '''
        Permutes theList using a random permutation.
        See p. 139 of "Seminumerical Algorithms, 2nd edition"
        by Donald Knuth, for more details.
        '''
        k = len(theList) - 1
        while k > 0:
            j = random.randint(0, k)
            theList[j], theList[k] = theList[k], theList[j]
            k = k - 1

    def bubbleSort(self, theList):
        '''
        Sorts the specified list in increasing order using the simplest version of bubble sort.
        '''
        for k in range(len(theList) - 1):
            for j in range(len(theList) - k - 1):
                self.comparisonCount += 1
                if theList[j] > theList[j + 1]:
                    theList[j], theList[j + 1] = theList[j + 1], theList[j]

    def selectionSort(self, theList):
        '''
        Sorts the specified list in increasing order using selection sort.
        '''
        for k in range(len(theList) - 1, 0, -1):
            indexOfMax = 0
            for j in range(1, k + 1):
                self.comparisonCount += 1
                if theList[j] > theList[indexOfMax]:
                    indexOfMax = j
            theList[k], theList[indexOfMax] = theList[indexOfMax], theList[k]

    def insertionSort(self, theList):
        '''
        Sorts the specified list in increasing order using insertion sort.
        '''
        for k in range(1, len(theList)):
            savedItem = theList[k]
            j = k - 1
            while j >= 0 and theList[j] > savedItem:
                self.comparisonCount += 1
                theList[j + 1] = theList[j]
                j = j - 1
            theList[j + 1] = savedItem

    def recursiveInsertionSort(self, theList, sublistLength=-1):
        '''
        Sorts the specified list in increasing order using a recursive
        insertion sort.
        '''
        if sublistLength == -1:
            sublistLength = len(theList)

        if sublistLength > 1:
            self.recursiveInsertionSort(theList, sublistLength - 1)
            savedItem = theList[sublistLength - 1]
            k = sublistLength - 2
            while k >= 0 and theList[k] > savedItem:
                self.comparisonCount += 1
                theList[k + 1] = theList[k]
                k = k - 1
            theList[k + 1] = savedItem

    def merge(self, theList, left, middle, right):
        '''
        Merges two sublists of the specified list.  The sublists to be
        merged are theList[left:middle+1] and theList[middle+1:], and their
        merged contents are to be stored in theList[left:right+1].  Each
        of the sublists is assumed to be sorted in increasing order before
        merge is called.  If this assumption is valid, then the resulting
        merged sublist will be in increasing order after the merge.
        '''
        mergedSublist = []
        currentLeft = left
        currentRight = middle + 1
        while currentLeft <= middle and currentRight <= right:
            self.comparisonCount += 1
            if theList[currentLeft] <= theList[currentRight]:
                mergedSublist.append(theList[currentLeft])
                currentLeft += 1
            else:
                mergedSublist.append(theList[currentRight])
                currentRight += 1

        if currentLeft <= middle:
            mergedSublist.extend(theList[currentLeft:middle+1])

        if currentRight <= right:
            mergedSublist.extend(theList[currentRight:right+1])

        theList[left:right+1] = mergedSublist


    def mergeSort(self, theList, left=-1, right=-1):
        '''
        Sorts the specified list in increasing order using insertion sort.
        If left and right are specified, then only the sublist theList[left:right+1]
        will be sorted.  Otherwise, the whole list will be sorted.
        '''
        if left == -1:
            self.mergeSort(theList, 0, len(theList) - 1)
        elif left < right:
            middle = (left + right) / 2
            self.mergeSort(theList, left, middle)
            self.mergeSort(theList, middle + 1, right)
            self.merge(theList, left, middle, right)


if __name__ == '__main__':
    # Get N from the command line (or print a usage statement if the
    # program was called incorrectly.
    if len(sys.argv) >= 2 and sys.argv[2].isdigit():
        algorithm = sys.argv[1]
        N = int(sys.argv[2])
        verbose = (len(sys.argv) == 4 and sys.argv[3] == 'verbose')
    else:
        print
        print 'Usage: python %s algorithm listLength [verbose]' % sys.argv[0]
        print
        print 'The algorithm parameter must be one of: merge, insertion, recursiveinsertion, selection, or bubble'
        print
        print 'For example,\n\n\tpython %s selection 10 verbose\n' % sys.argv[0]
        print 'will sort a 10-element list using selection sort, and will print out'
        print 'the "verbose" information--that is, the before and after versions of the list.'
        print 'With or without "verbose", the sorting time will be reported.'
        print
        sys.exit(1)

    # Create a Sorter object and a list of integers.
    sorter = Sorter()
    listOfIntegers = range(N)

    # Shuffle the list.
    sorter.shuffle(listOfIntegers)
    if verbose:
        print listOfIntegers

    # Sort the list.
    startTime = time.time()

    if algorithm == 'merge':
        sorter.mergeSort(listOfIntegers)
    elif algorithm == 'insertion':
        sorter.insertionSort(listOfIntegers)
    elif algorithm == 'recursiveinsertion':
        sorter.recursiveInsertionSort(listOfIntegers)
    elif algorithm == 'bubble':
        sorter.bubbleSort(listOfIntegers)
    elif algorithm == 'selection':
        sorter.selectionSort(listOfIntegers)
    else:
        print '"%s" is an unknown algorithm' % algorithm

    endTime = time.time()

    if verbose:
        print listOfIntegers

    print
    print '%s (N = %d): %d comparisons' % (algorithm, len(listOfIntegers), sorter.comparisonCount)
    print '%s (N = %d): %f seconds' % (algorithm, len(listOfIntegers), endTime - startTime)
    print