'''
   20211028
   
   Robin Dawes
   
   QuickSort
   
   This version modifies the original list and returns None
   
   It sorts the values in-place
'''


   
def partition(a_list, first, last):
   ''' partitions the list, puts the pivot value in place, and returns the location
      of the pivot value
      
      Parameters
         a_list - a list of objects or values that can be compared and ordered
         first - a numeric value indicating the start of the part of a_list to be sorted
         last - a numeric value indicating the end of the part of a_list to be sorted     
   '''
   
   pivot = a_list[first]         # save the pivot value for easy comparisons
   left = first
   right = last
   
   # The goal of the following loop is to end with left pointing to the last
   # position where there is a value <= pivot, and right pointing to the first 
   # position where there is a value > pivot, if any
   
   # Start with left = first (guaranteed to be <= pivot)
   # Start with right = last (may not be > pivot)
   # As long as left < right:
   #    Move left rightward until left == right or we find something > pivot 
   #    Move right leftward until left == right or we find something <= pivot
   #    if left < right
   #        swap and continue
   #    else  
   #        if a_list[left] > pivot, left -= 1
   # Put the pivot value in its proper location
   
   while left < right:           # continue until the partitioning is complete   
      # advance left marker to the right until it needs to stop
      while left < right and a_list[left] <= pivot:
         left += 1
      #advance right marker to the left until it needs to stop
      while left < right and a_list[right] > pivot:
         right -= 1
      # if the markers have not met, swap the values they point to   
      if left < right:
         temp = a_list[left]
         a_list[left] = a_list[right]
         a_list[right] = temp
   
   # when the loop exits, left may be one location to the right of where it
   # should be.  Check for this and move back if necessary
   if a_list[left] > pivot:
      left -= 1
      
   # place the pivot value in its correct location   
   a_list[first] = a_list[left]
   a_list[left] = pivot
   
   # return the new position of the pivot value
   return left
   
def quicksort(a_list):
   '''initiates the recursive sort
   
      Parameter:
         a_list must be a list of objects or values that can be
           compared and ordered
   '''
   
   quicksort_rec(a_list, 0, len(a_list) - 1)
   

def quicksort_rec(a_list, first, last) :
   '''applies the recursive quicksort algorithm
   
      Parameters
         a_list - a list of objects or values that can be compared and ordered
         first - a numeric value indicating the start of the part of a_list to be sorted
         last - a numeric value indicating the end of the part of a_list to be sorted     
   
   '''
   if first >= last:
      return 
   else:
      pivot_pos = partition(a_list, first, last)
      quicksort_rec(a_list, first, pivot_pos - 1)
      quicksort_rec(a_list, pivot_pos + 1, last)
   
# main

   
import random

# create a list of randomly chosen integers
values = random.sample(range(1, 100), 15)

print("\n")
print("Before sort:", values)
quicksort(values)
print("After sort", values)
print("\n")


print("Test on set that is already sorted:")
print("Before sort: ", values)
quicksort(values)
print("After sort: ", values)
print("\n")

print("Test on set that is in reverse order:")
values.reverse()
print("Before sort:", values)
quicksort(values)
print("After sort:",values)