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

   Jed Yang, 2016-11-06

   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 "comparisonCount" variable.

   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.comparisonCount = 0

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

   def bubbleSort(self, array):
      '''
      Sorts the specified list in increasing order using the simplest version
      of Bubble Sort: swap adjacent pairs that are inverted.
      '''
      n = len(array)
      for i in range(n):
         for j in range(n - i - 1):
            self.comparisonCount = self.comparisonCount + 1
            if array[j] > array[j+1]:
               array[j], array[j+1] = array[j+1], array[j]

   def selectionSort(self, array):
      '''
      Sorts the specified list in increasing order using Selection Sort:
      select the min and swap it into its correct place.
      '''
      n = len(array)
      for i in range(n):
         minIndex = i
         for j in range(i+1, n):
            self.comparisonCount = self.comparisonCount + 1
            if array[j] < array[minIndex]:
               minIndex = j
         array[i], array[minIndex] = array[minIndex], array[i]

   def insertionSort(self, array):
      '''
      Sorts the specified list in increasing order using Insertion Sort:
      insert the next element into a sorted prefix.
      '''
      n = len(array)
      for i in range(1, n):
         j = i
         while j > 0 and array[j] < array[j-1]:
            self.comparisonCount = self.comparisonCount + 1
            array[j], array[j-1] = array[j-1], array[j]
            j = j - 1

   def recursiveInsertionSort(self, array, n=None):
      '''
      Sorts the specified list in increasing order using a recursive
      implementation of Insertion Sort.

      If n is specified, only sort the first n elements.
      '''
      # by default, sort the entire list
      if n == None:
         n = len(array)

      # short lists are always sorted
      if n <= 1:
         return

      # recursively sort the first n - 1 elements
      self.recursiveInsertionSort(array, n - 1)

      # insert the last element into place by swapping
      j = n - 1
      while j > 0 and array[j] < array[j-1]:
         self.comparisonCount = self.comparisonCount + 1
         array[j], array[j-1] = array[j-1], array[j]
         j = j - 1

   def merge(self, listA, listB):
      '''
      Merges two sorted lists into one sorted list.

      Returns the merged list.
      '''
      a = 0
      b = 0
      listC = []
      while a < len(listA) and b < len(listB):
         self.comparisonCount = self.comparisonCount + 1
         if listA[a] < listB[b]:
            listC.append(listA[a])
            a = a + 1
         else:
            listC.append(listB[b])
            b = b + 1
      # one of listA or listB is exahusted, so precisely one loop below will run
      while a < len(listA):
         listC.append(listA[a])
         a = a + 1
      while b < len(listB):
         listC.append(listB[b])
         b = b + 1
      return listC

   def mergeSort(self, array, left=None, right=None):
      '''
      Sorts the specified list in increasing order using Merge Sort:
      merge recursively sorted halves.

      If left and right are specified, then only the sublist array[left:right]
      will be sorted.  Otherwise, the whole list will be sorted.
      '''
      # by default, sort the entire list
      if left == None:
         left = 0
      if right == None:
         right = len(array)

      if right - left > 1:
         middle = (left + right) // 2
         self.mergeSort(array, left, middle)
         self.mergeSort(array, middle, right)
         array[left:right] = self.merge(array[left:middle], array[middle:right])

def main():
   # Get N from the command line (or print a usage statement if the program was
   # called incorrectly).
   if len(sys.argv) >= 3 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: python3 {0} algorithm listLength [verbose]'.format(sys.argv[0]))
      print()
      print('The algorithm parameter must be one of: merge, insertion, recursiveinsertion, selection, or bubble')
      print()
      print('For example,\n\n\tpython3 {0} selection 10 verbose\n'.format(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 = list(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('"{0}" is an unknown algorithm.'.format(algorithm))
      sys.exit(2)

   endTime = time.time()

   if verbose:
      print(listOfIntegers)

   print()
   print('{0} (N = {1}): {2} comparisons'.format(algorithm, len(listOfIntegers), sorter.comparisonCount))
   print('{0} (N = {1}): {2:f} seconds'.format(algorithm, len(listOfIntegers), endTime - startTime))
   print()

if __name__ == '__main__':
   main()