# selection sort: make repeated passws through the list,
# moving the smallest number to the beginning of the list
# and advancing the beginning of the list each time through;
# stop when there is only 1 element left in the list
#
# we print 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

#
# this is the selection sort routine
#
def selectsort(numlist):
        # we track the number of comparisons and swaps (exchanges)
        global swaps, compares
        # get length of list
        n = len(numlist)

        # you will make a number of passes through the list,
        # each time starting one element further on, as the
        # previous pass put the smallest element in the list first
        for low in range(0, n):
                # print the current state of the list?
                if showintermediate:
                        print("         ", numlist)
                # assume the smallest element comes first
                min = numlist[low]
                minindex = low
                # now find index of the smallest element 
                for i in range(low+1, n):
                        # doing another comparison
                        compares += 1
                        # found something smaller; may be the smallest
                        # make note of the index and value, which is\
                        # the new minimum
                        if numlist[i] < min:
                                min = numlist[i]
                                minindex = i
                # minindex is now the index of the smallest element
                # of the list, so exchange it and the first element
                # of the list
                if minindex != low:
                        swaps += 1
                        numlist[low], numlist[minindex] = numlist[minindex], numlist[low]

#
# 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
        selectsort(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()