In [1]:

    

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


    

In [2]:

    

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


    

In [3]:

    

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)


    

In [4]:

    

def partition(a,p,r):
    comp=0
    i = p-1
    pivot = a[p]
  
    for j in range(p,r):
        comp+=1
        if a[j]<=pivot:
            i+=1
            temp = a[j]
            a[j] = a[i]
            a[i] = temp
        
    temp = a[i+1]
    a[i+1] = a[r]
    a[r] = temp
    
    return i+1,comp


    

In [7]:

    

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()


    

In [8]:

    

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


    

    




n 3
mean 2.5
stdev 0.5
min 2
max 3






    













    




n 4
mean 4.66666666667
stdev 0.942809041582
min 4
max 6






    













    




n 5
mean 7.375
stdev 1.57619002661
min 6
max 10






    













    




n 8
mean 18.7392857143
stdev 4.56512446649
min 14
max 28






    

In [ ]: