# File: quicksort.py
#
# Testing the running time of Quicksort.
#

import time
import random

# REPS = 10000
REPS = 15


# Create a list of random numbers
#
def initRandom():
   global REPS

   A = []
   for i in range(0,REPS):
      A.append(random.randint(1,5*REPS))
   return A
      

# Checks if a list is actually sorted
#
def checkSorted(A):
   if len(A) <= 1: return TRUE
   previous = A[0]
   for i in range(1,len(A)):
      if previous > A[i]:
         return False
   previous = A[i]
   return True


# Partition for Quicksort. 
# Uses last item to pivot.
# Returns the position q of the pivot element.
# After partitions, items in A between start and q-1 (inclusive)
# are <= the pivot. The items in A between q+1 and end (inclusive)
# are > the pivot.
# Pivot is moved to index q.

def partition(A,start, end):
   x = A[end-1]
   i = start - 1
   for j in range(start, end-1):

      # print("i =", i, "j =", j, "x =", x)
      # print(A)

      if A[j] <= x:
         i = i + 1
         A[i], A[j] = A[j], A[i] # swap

   A[i+1], A[end-1] = A[end-1], A[i+1]  # swap
   return(i+1)
   

# Recursive implementation of Quicksort
#
def quickSort(A, start, end):

   # print("Quicksort: start =", start, "end = ", end)

   if start >= end-1: return 

   q = partition(A, start, end)
   # print("Partition: q =", q, A)
   quickSort(A, start, q)
   quickSort(A, q+1, end)

   return


def main():

   random.seed()

   aList = initRandom()
   print("Before: ", aList)

   # Uncomment if you want to just test partition()
   #
   # q = partition(aList, 0, len(aList))
   # print("q =", q)
   # print(aList)
   # exit()

   start = time.time()

   quickSort(aList, 0, len(aList))

   finish = time.time()
   print("Elapsed time =", finish - start, "seconds")

   if not checkSorted(aList):
      print("****List not sorted!****")
   else:
      print("+++ List is sorted +++")

   # print("After: ", aList)


main()