### Sorting algorithms and timings.

# The timing operations of this program only work on linux.
import timing
import time
import sys
from random import *

###### bubblesort

def bubble(A):
    print "write this one yourself"
# bubble


######## Swap sort: swap the largest element to the end

# find index of largest element in the array UPTO index endi

def maxi(A,endi):
    if endi<0 or endi>=len(A): raise "parameter error"  # error check
    mi = 0  # the index to be returned
    i = 1   # loop counter
    while i<= endi:
        if A[i] > A[mi]: mi = i
        i +=1
    return mi
# maxi

def swapsort(A):  # keep swapping largest value to end of array
    i = len(A)-1  # start at end
    while i>0:     # last element naturally falls into place
        mi = maxi(A,i)
        A[i],A[mi] = A[mi],A[i]  # swap largest to correct position
#        A[i], A[ maxi(A,i) ] = A[ maxi(A,i) ], A[i] # inefficient
        i = i-1
# swapsort


######## Quick sort  (non-destructive): ############

# return index of first element out of order, -1 if none exists
def ndfindpivot(A):
    an = -1
    i =0
    while i<len(A)-1 and an==-1:
        if A[i]>A[i+1]: an = i+1
        i += 1
    return an
#findpivot

# First version of partition is non-destructive; returns pair of arrays

def ndpartition(pi,A): # parition A according to pivot at index pi
    pivot = A[pi]
    L = []  # left partition
    R = []  # right partition
    i = 0
    while i<len(A):
        if A[i]<=pivot: L.append(A[i])
        else: R.append(A[i])
        i +=1
    return (L,R)
# ndpartition

# overall quicksort procedure, non-destructive
def ndquicksort(A):
    pi = ndfindpivot(A)
    if (pi != -1):  # if there is a pivot, otherwise A already sorted
        (L,R) = ndpartition(pi,A)
        LS = quicksort(L)
        RS = quicksort(R)
        return LS+RS   # return the concatenation of two partitions
    else:
        return A
# non-destructive quicksort


########## Quicksort  (destructive)  ##########################

# find position of first element out of order, -1 if none
def pivot(A,start,end):  # active range is A[start:end]
    i = start+1
    answer = -1  # there exists type of function
    while i<end and answer == -1:
        if A[i]<A[i-1]: answer = i
        i +=1
    # while
    return answer
#pivot

# partition array into portion <= pivot, and portion > pivot using two indices
# index j will keep track of the end of the first partition + 1, index i will
# go through the list and swap every element < pivot with j, and advance j.
# This function will also return the end value of j, which marks start of
# second partition.
def partition(A,piv,start,end):
    i = start  # go through A one by one.
    j = start  # first available "slot" for the left partition.
    while i<end:
        if A[i] <= piv: # swap with A[j]
            A[j], A[i] = A[i], A[j]
            j = j+1  # j now points to next available slot.
        i = i+1
    #while
    return j
#partition: note also that this is a *destructive* function

# quicksort: find pivot, partition, and recursively sort each partition.
# The active partition is defined by A[start:end] (start to end-1)
def quicksort(A,start,end):
    pi = pivot(A,start,end)
    if (pi != -1):  # else the array is already sorted
        piv = A[pi] # value of pivot element
        j = partition(A,piv,start,end) # partion A into A[start:j] and A[j:end]
        quicksort(A,start,j)
        quicksort(A,j,end)
    # if
#quicksort

A = [5,8,7,3,19,10,4,9,6,12,2,0,1]
quicksort(A,0,len(A))
print A
##########

if len(sys.argv)>1:
    size = int(sys.argv[1])  # size of test array as command-line argument
else: size = 2000

A,B,C = [],[],[]
i = 0
while i<size:
    r = random()*100000
    A.append( r )
    B.append( r )
    C.append( r )
    i +=1
# 2 identical random arrays


timing.start()
bubble(A)
timing.finish()

m1 = timing.milli()


timing.start()
swapsort(A)
timing.finish()

m2 = timing.milli()

timing.start()
quicksort(A,0,len(A))
timing.finish()

m3 = timing.milli()

print "bubblesort time: ",m1," ms"
print "swapsort time: ",m2," ms"
print "quicksort time: ",m3," ms"