# quicksort: pick an element of the list (called the pivot); then
# move all elements less than the pivot before it, and all elements
# greater than the pivot after it; then (recursively) sort each half
#
# we print the pivot and the current state of the list each time through
#
# also count (and print) the number of comparisons and
# exchanges
# 
# Matt Bishop   ECS 36A, Winter 2019
#

#
# set this to False to print *only* the original (unsorted)
# and the final (sorted) lists
# set to True to print the intermediate (partially sorted) lists
#
showintermediate = True

#
# we will generate a list of this many numbers
# and then shuffle them 7 times using shuffle()
# from the random module
#
import random
nnums = 20

# set the number of swaps and comparisons to 0
swaps = 0
compares = 0

#
# pick the pivot; this partitions the list into two parts
# the list is the part of numlist with index low to index high
# 
def partition(numlist, low, high):
        global swaps, compares
        # pick the pivot
        pivot = numlist[high]

        # now go through the list; at the end of this loop,
        # i is the index where the pivot goes; so everything
        # less than the pivot goes to before that index
        i = low
        for j in range(low, high+1):
                # a comparison with the pivot
                compares += 1
                if numlist[j] < pivot:
                        # now swap this with what's at index i
                        # and advance index i by 1, to keep what
                        # is before the index to where the pivot
                        # will go
                        swaps += 1
                        numlist[i], numlist[j] = numlist[j], numlist[i]
                        i += 1

        # now put the pivot in the right place
        # remember the pivot is at the end (index high)
        swaps += 1
        numlist[i], numlist[high] = numlist[high], numlist[i]

        # print the current state of the list?
        if showintermediate:
                print("pivot %2d:" % pivot)

        # and return the index of the pivot
        return i

# use selection sort to sort the word list
# start at index 0 (first index), find the smallest element in the rest of the list
# if it's less than the value at the first index, swap
# repeat, advancing the first index until you reach the end of the list
# globals: wordlist, list to search
def quicksort(numlist, low, high):
        # print the current state of the list?
        if showintermediate:
                print("         ", numlist)
        if low < high:
                p = partition(numlist, low, high)
                quicksort(numlist, low, p - 1)
                quicksort(numlist, p + 1, high)
                # print the current state of the list?
                if showintermediate:
                        print("         ", numlist)

def qsort(numlist):
        quicksort(numlist, 0, len(numlist)-1)
#
# generate a list of numbers
# we just put the first nnums number into a list (0 .. nnums-1)
# and then shuffle it 7 times
#
def loadnums():
        # generate the list; use range and convert it
        numlist = list(range(nnums))

        # now shuffle 7 times; in theory, this makes
        # it as random as possible
        for i in range(0, 7):
                random.shuffle(numlist)
                
        # and return the list!
        return numlist

#
# this puts it all together
#
def main():
        # we need to print these
        global compares, swaps
        
        # get the list
        # if it's empty, quit (just in case :)
        nums = loadnums()
        if nums == []:
                return

        # print the initial list
        print("Unsorted:", nums)
        
        # sort the list
        qsort(nums)

        # print the sorted list and the relevant statistics
        print("  Sorted:", nums)
        print("This took {} comparisons and {} swaps".format(compares, swaps))

#
# and we're off!
#
main()