""" A naive version of quicksort (first of the list is the pivot)"""

from random import *

def quicksort( myList, first, last ):
    """ Sort the given list using the quicksort algorithm. Sorts the
        portion of the list between the first and last indices (inclusive).
    """
    # base case: done when the indices touch or overlap.
    if first >= last: return

    # recursive case: partition the myList and recurse on both sides
    split = partition( myList, first, last )
#    split = partitionA( myList, first, last )
    quicksort( myList, first, split-1 )
    quicksort( myList, split+1, last )

def partitionA( theSeq, first, last ):
    """A slightly different version of partition.
       This version moves from both end of the list and swaps with
       the pivot as needed. (Textbook author Necaise's solution.
    """
    # Save a copy of the pivot value.
    pivot = theSeq[first]
  
    # Find the pivot position and move the elements around the pivot.
    left = first + 1
    right = last
    while left <= right :
        # Find the first key larger than the pivot.
        while left <= right and theSeq[left] < pivot : 
            left += 1                                  
      
        # Find the last key in the sequence that is smaller than the pivot.
        while right >= left and theSeq[right] >= pivot : 
            right -= 1                                    
      
        # Swap the two keys if we have not completed this partition.
        if left < right :
            tmp = theSeq[left]
            theSeq[left] =  theSeq[right]
            theSeq[right] = tmp
      
    # Put the pivot in the proper position.
    if right != first :                             
        theSeq[first] = theSeq[right]
        theSeq[right] = pivot
  
    # Return the index position of the pivot value.
    return right

def partition( myList, first, last ):
    """ Partition the given list into two parts. The first part will
        contain smaller values, the second part will contain larger values.
        There will be a pivot value between them. Partitions the
        portion of the list between the first and last indices (inclusive).
        Return the index of the pivot element.
    """

    # Improved versions of quicksort should make better choice of 'pivot'
    lastSmall = first
    
    # Seperate the list into "pivot, smalls, lastSmall, larges".
    for i in range( first+1, last+1 ): # first+1 ... last (inclusive)
        # if myList[i] is small, swap it onto the 'small' side.
        if myList[ i ] <= myList[ first ]: 
            lastSmall = lastSmall + 1
            swap( myList, lastSmall, i )
        
    # Swap the pivot with lastSmall to get "smalls, pivot, larges".
    swap( myList, first, lastSmall )

    # Return the location of the pivot
    return lastSmall

def swap( myList, first, second ):
    """ Swap the items at the first and second indices in the given list.
        Assumes the indices are legal and occupied in the list.
    """
    tmp = myList[ first ]
    myList[ first ] = myList[ second ]
    myList[ second ] = tmp