Hwk2.py

"""
@Author Kent Libby
This was compiled against python 2
To run the script use python2 Hwk2.py
"""
import random
import math


def create_array(num_items):
    """
    :param num_items: size of array
    :type num_items: int
    :return: randomized array of [0->1000] of size szie
    """
    range_elements=1000
    elements = [0 for i in range(num_items)]
    for i in range(len(elements)):
        elements[i] = random.randint(1, range_elements)

    return elements


def quicksort():
    """

    :param array_in: the array to sort
    :return: the sorted array
    """
    # intitialize the arrays
    size_to_sort=100
    to_sort= create_array(size_to_sort)
    # to_sort=[2, 0, 1, 4, 6]
    # Get the intializations for the actual alogrithm ready to go
    start_point=0
    end_point=len(to_sort)

    # do the swap to get the "ideal" pivot
    pivot_loc = int(math.floor((end_point-start_point) / 2))
    to_sort[pivot_loc], to_sort[end_point-1] = to_sort[end_point-1], to_sort[pivot_loc] # get the pivot in place
    print to_sort  # print the initial condition after the pivot has been moved

    sorted_arr=quicksort_alg(to_sort, start_point, end_point)


def quicksort_alg(to_sort, start_point, end_point):
    """

    :param to_sort: the list to sort
    :param start_point: the point to start looking through the list
    :param end_point: the point to stop (the previous pivot)
    :return: the sorted array
    """

    # set up all the variables for running through the array
    # start_point and end_point CANNOT CHANGE
    start = start_point
    pivot = end_point-1
    end = pivot

    if start_point-end_point == 0:
        return to_sort

    while start != end:
        if to_sort[start] <= to_sort[pivot]:  # if the value isn't greater than the pivot
            start += 1  # ignore it when searching for something to swap

        elif to_sort[end] >= to_sort[pivot]:  # similarly if the other end is larger than the pivot, move on
            end -= 1

        if to_sort[end]<to_sort[pivot]<to_sort[start]:
            to_sort[start], to_sort[end] = to_sort[end], to_sort[start]

    # this will be hit after the pointers cross ie are equal
    to_sort[start], to_sort[pivot] = to_sort[pivot], to_sort[start]

    pivot=start  # this changes the location of the pivot to where it was moved so the elements can be partitioned

    quicksort_alg(to_sort, start_point, pivot)  # this will sort from the start point and end at the pivot (which will
    # make the algorithm go to just before the pivot)
    quicksort_alg(to_sort, pivot + 1,
                  end_point)  # this will start from after the previous pivot and work towards the end
    print to_sort
    return to_sort

if __name__ == "__main__":
    quicksort()