Skip to content

Instantly share code, notes, and snippets.

# Kdoje/Hwk2.py Created Nov 8, 2018

 """ @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 join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.