"""
Name: Joshua Wallace
UPI: jwal629
ID: 8738173

This program has four methods inside of it: get_kth_smallest1 and get_kth_smallest2 (and its corresponding sift_down method) methods are
Selection and Heap sort methods respectively, and sort a given list and return the element in the integer position
(required_position) of the list. So, if a list was a = [3, 2, 1], it would be sorted so that it is a = [1, 2, 3], and if
required_position = 2, then the value returned would be 3, as a[2] = 3. Both methods use their own respective sorting algorithm,
with Selection sort having a big O notation of O(n^2), and Heap sort having a big O notation of O(n * log n)
(therefore, the Heap sort is much faster than the Selection sort).

To verify that the Heap sort is the fastest of the two, the fourth method, test_kth_smallest, calls both methods get_kth_smallest1
and get_kth_smallest2, and gives them randomised lists of a specific size to sort, timing how long it takes for the two different
sorting algorithms to sort their lists. It increases the size of the list by ten five times, so how the algorithm tackles sizes
of an increasing magnitude is easily observed.
"""

import random
import time

def get_kth_smallest1(array, required_position): # Selection sort.

    for i in range(len(array)):
        smallest_value = min(array[i:])
        index = array[i:].index(smallest_value) 
        array[i + index] = array[i]
        array[i] = smallest_value

    return array[required_position]

def get_kth_smallest2(array, required_position): # Heap sort.

    length = (len(array) - 1)
    n = length//2
    
    for i in range(n, -1, -1):
        sift_down(array, i, length)

    for i in range(length, 0, -1):
        if array[0] > array[i]:
            temp = array[0]
            array[0] = array[i]
            array[i] = temp
            sift_down(array, 0, i - 1)

    return array[required_position]

def sift_down(array, first, last):
    
    largest = 2 * first + 1
    
    while largest <= last:
        if (largest < last) and (array[largest] < array[largest + 1]):
            largest += 1
        if array[largest] > array[first]:
            temp = array[largest]
            array[largest] = array[first]
            array[first] = temp
            first = largest
            largest = 2 * first + 1
        else:
            return

def test_kth_smallest(size):

    x = size

    print("Note that the k values printed below, when indicating the 'kth' smallest element in a list, is actually (k + 1), as the 1st smallest element in a list will be the element at array[0], 2nd smallest element will be at array[1] etc. \n")

    print("Selection sort: \n")

    for i in range(0, 5): # Selection sort
        k = random.randint(5, 25)
        array = []
        while len(array) <= 25:
            array.append(random.randint(0, 25))
        print(str(i + 1) + ": Unsorted array:", array)
        print("The " + str(k + 1) + "th smallest value in the sorted list is " + str(get_kth_smallest1(array, k)) + ".")
        print("Array sorted using Selection sort:", array)
        print("The value of k is:", k, "\n")

    print("Heap sort: \n")

    for i in range(0, 5): # Heap sort
        k = random.randint(5, 25)
        array = []
        while len(array) <= 25:
            array.append(random.randint(0, 25))
        print(str(i + 1) + ": Unsorted array:", array)
        print("The " + str(k + 1) + "th smallest value in the sorted list is " + str(get_kth_smallest2(array, k)) + ".")
        print("Array sorted using Heap sort:", array)
        print("The value of k is:", k, "\n")
    
    for i in range(0, 5): # Time taken by Selection sort
        while len(array) <= size:
            array.append(random.randint(0, 10000))
        x1 = time.clock()
        get_kth_smallest1(array, k)
        y1 = time.clock()
        print(str(i + 1) +". Time taken for Selection sort to sort list of size", str(size) + ":", "{0:.7f}".format((y1 - x1) * 1000), "milliseconds.")
        size *= 10

    print("\n")

    size = x

    for i in range(0, 5): # Time taken by Heap sort
        while len(array) <= size:
            array.append(random.randint(0, 10000))
        x2 = time.clock()
        get_kth_smallest2(array, k)
        y2 = time.clock()
        print(str(i + 1) + ". Time taken for Heap sort to sort list of size", str(size) + ":", "{0:.7f}".format((y2 - x2) * 1000), "milliseconds.")
        size *= 10

test_kth_smallest(1) # Size given is so small as larger values take far longer to process