import itertools
import numpy as np
import matplotlib.pyplot as plt
#%matplotlib inline

dec = {}
dec[0] = []
def quickSort(alist,times):
   comp = [0]
   quickSortHelper(alist,0,len(alist)-1,comp)
   times.append(comp[0])

def quickSortHelper(alist,first,last,comp):
   if first<last:

       r = partition(alist,first,last)
       splitpoint = r[0]
       tmp = comp.pop()
       comp.append(tmp+r[1])

       quickSortHelper(alist,first,splitpoint-1,comp)
       quickSortHelper(alist,splitpoint+1,last,comp)


def partition(array,p,r):
    pivot = array[r]
    comp = 0
    i = p
    j = p
    while(j<r):
        dec[0].append(1)
        comp += 1
        if array[j]<=pivot:
            swap(array,i,j)
            i+=1
        j+=1
    swap(array,i,r)
    return i, comp


def swap(array,i,j):
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp



def quickSortTimeDistrib(k):

    # Create an array of n elements
    n=k
    x = []
    for i in range(1,n+1):
        x.append(n+1-i)

     # Run quicksort for each permunation
    tlist =[]
    for p in itertools.permutations(x):
        quickSort(np.asarray(p),tlist)

    print "n",n
    print "mean",np.mean(tlist)
    print "stdev",np.std(tlist)
    print "min",min(tlist)
    print "max",max(tlist)
    bins = []

    for k in range(max(tlist)-min(tlist)+2):
        bins.append(min(tlist)-0.5+k)

    plt.hist(tlist, bins)
    plt.title("Number of comparison of Quicksort for all permutaions")
    plt.xlabel("Comparisons of elements")
    plt.ylabel("Number of cases")
    plt.grid(True)
    plt.show()


quickSortTimeDistrib(3)
quickSortTimeDistrib(4)
quickSortTimeDistrib(5)