Instantly share code, notes, and snippets.

Embed
What would you like to do?
"""
@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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment