'''
    sorter.py
    Jeff Ondich, updated 6 November 2018

    Implementations of several sorting algorithms

    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 placed the sorting functions inside a class to give all of them
    easy access to a comparison_count variable. Study where I have placed
    the "self.comparison_count += 1" lines. Why did I put them where I
    put them?

    Run "python3 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.comparison_count = 0

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

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

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

    def insertion_sort(self, the_list):
        ''' Sorts the specified list in increasing order using insertion sort. '''
        k = 1
        N = len(the_list)
        while k < N:
            saved_item = the_list[k]
            j = k - 1
            while j >= 0 and the_list[j] > saved_item:
                self.comparison_count += 1
                the_list[j + 1] = the_list[j]
                j = j - 1
            the_list[j + 1] = saved_item
            k = k + 1

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

        if sublist_length > 1:
            self.recursive_insertion_sort(the_list, sublist_length - 1)
            saved_item = the_list[sublist_length - 1]
            k = sublist_length - 2
            while k >= 0 and the_list[k] > saved_item:
                self.comparison_count += 1
                the_list[k + 1] = the_list[k]
                k = k - 1
            the_list[k + 1] = saved_item

    def merge(self, the_list, left, middle, right):
        ''' Merges two sublists of the specified list.  The sublists to be
            merged are the_list[left:middle+1] and the_list[middle+1:], and their
            merged contents are to be stored in the_list[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. '''
        merged_sublist = []
        current_left = left
        current_right = middle + 1
        while current_left <= middle and current_right <= right:
            self.comparison_count += 1
            if the_list[current_left] <= the_list[current_right]:
                merged_sublist.append(the_list[current_left])
                current_left += 1
            else:
                merged_sublist.append(the_list[current_right])
                current_right += 1

        if current_left <= middle:
            merged_sublist.extend(the_list[current_left:middle+1])

        if current_right <= right:
            merged_sublist.extend(the_list[current_right:right+1])

        the_list[left:right+1] = merged_sublist


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

def print_usage_statement(program_name):
    print('''
Usage: python3 {0} algorithm list-length [verbose]

The algorithm parameter must be one of: merge, insertion, recursiveinsertion, selection, or bubble

For example,

    python3 {0} selection 10 verbose

will sort a 10-element list using selection sort, and will print out
the "verbose" information--that is, the before and after versions of the list.
With or without "verbose", the sorting time will be reported.
'''.format(program_name))


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_usage_statement(sys.argv[0])
        sys.exit(1)

    # Create a Sorter object and a list of integers.
    sorter = Sorter()
    list_of_integers = [k for k in range(N)]

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

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

    if algorithm == 'merge':
        sorter.merge_sort(list_of_integers)
    elif algorithm == 'insertion':
        sorter.insertion_sort(list_of_integers)
    elif algorithm == 'recursiveinsertion':
        sorter.recursive_insertion_sort(list_of_integers)
    elif algorithm == 'bubble':
        sorter.bubble_sort(list_of_integers)
    elif algorithm == 'selection':
        sorter.selection_sort(list_of_integers)
    else:
        print('"{0}" is an unknown algorithm'.format(algorithm))

    end_time = time.time()

    if verbose:
        print(list_of_integers)

    print()
    print('{0} (N = {1}): {2} comparisons'.format(algorithm, len(list_of_integers), sorter.comparison_count))
    print('{0} (N = {1}): {2:.3f} seconds'.format(algorithm, len(list_of_integers), end_time - start_time))
    print()