import time
import random
import sys
sys.setrecursionlimit(1000000)


##Main function call to run tests on 2 equal arrays of size num_elements
        ##time arrays through both algorithms
        ##and print both time of execution and sorted array to screen
def run_sort_tests(num_elements):
    num_elements=num_elements
    num_array=[]
    num_array2=[]
    num_array,num_array2=create_arrays(num_array,num_array2,num_elements)
    print "\nUnsorted Array:\n",num_array,"\nend unsorted\n\n"

######Time Bubble  and print array/time
    start = time.clock()
    bubbleSort(num_array, num_elements)
    end = time.clock()
    total_time = end - start

    #uncomment to see sorted array    
    print num_array
    print "\nBubbleSort time for ",num_elements," elements: ",total_time,"\n"

######Time Quick Sort print array/time
    start = time.clock()
    quickSort(num_array2,0,num_elements-1)
    end = time.clock()
    total_time = end - start
    
    #uncomment to see sorted array
    print num_array2
    print "\nQuickSort time for ",num_elements," elements: ",total_time,"\n"

##Function to create 2 equal arrays of size num_elements
def create_arrays(array1,array2,num_elements):
    array1=[0]*num_elements
    for i in range(0,num_elements):
        array1[i] = random.randint(0,1000)
    array2=array1
    return array1,array2


##Bubble sort algorithm
def bubbleSort(nums,elements):
    i=elements-1
    j=1
    while i>=0:        
        j=1
        while j<=i:           
            if nums[(j-1)]>nums[j]:
                temp=nums[j-1]
                nums[j-1]=nums[j]
                nums[j]=temp
                
            j+=1
        i-=1
    
#Partition Function for use within quick sort algorithm
def partition(nums, L, R):
    pivot = nums[R]
    pivot_index=R
    j = L                         
    i = R+1
    
    loop=1
    while loop:
        j+=1
        while nums[j]<pivot:                        
                             

            if j == i:                  
                loop = 0                     
                break
            j +=1
        i -=1  
        while nums[i]>pivot:                        
                                 
            if i == j:                  
                loop=0              
                break
            i -=1  
        temp=nums[j]
        nums[j]=nums[i]
        nums[i]=temp
        if i>=j:
            break
        
    temp=nums[j]
    nums[j]=nums[i]
    nums[i]=temp   
    nums[pivot_index]=nums[i]
    nums[i]=pivot                      
    return i                                 

##Quick Sort Function algorithm
def quickSort(nums, L, R):
    if L < R:                           
        piv = partition(nums, L, R)    
        quickSort(nums, L, piv-1)       
        quickSort(nums, piv+1, R)
    return
  





##run 3 tests
run_sort_tests(10)
run_sort_tests(100)
run_sort_tests(1000)
run_sort_tests(10000)
run_sort_tests(100000)


raw_input("")