In [19]:

    

import random
import statistics
import matplotlib.pyplot as plt
%matplotlib inline


    

In [20]:

    

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


    

In [21]:

    

def randomquicksorthelper(alist,first,last,comp):
    if first<last:
        r = randompartition(alist,first,last)
        splitpoint = r[0]
        tmp = comp.pop()
        comp.append(tmp+r[1])
    
        randomquicksorthelper(alist,first,splitpoint-1,comp)
        randomquicksorthelper(alist,splitpoint+1,last,comp)


    

In [22]:

    

def randompartition(alist,first,last):
  
   
    pivotvalue = alist[first]
    i =first-1
    compspart=0
    for j in range(first,last-1):

        compspart = compspart + 1
        if alist[j]<=pivotvalue:
            i+=1
            temp = alist[j]
            alist[j] = alist[i]
            alist[i] = temp
        temp = alist[i+1]
        alist[i+1] = alist[last]
        alist[last] = temp

    return i+1,compspart


    

In [23]:

    

def randomquicksorttimedistrib(s,r):
    
    # Create an array of 1 .. n  
    n=s
    runs=r
    x = []
    for i in range(1,n+1):
        x.append(n+1-i)
    
     # Run quicksort for each permutation
    tlist =[]
    for p in range(1,runs+1):
            y = list(x)
            randomquicksort(y,tlist)
          
        
    plt.hist(tlist)
    plt.title("Number of comparison of Quicksort for all permutaions")
    plt.xlabel("Comparisons of elements")
    plt.ylabel("Frequency")
    plt.show()
    
    print("n",n)
    print("runs",runs)
    print("mean",statistics.mean(tlist))
    print("stdev",statistics.stdev(tlist))
    print("min",min(tlist))
    print("max",max(tlist))


    

In [24]:

    

randomquicksorttimedistrib(100,10000)


    

    













    




n 100
runs 10000
mean 2450
stdev 0.0
min 2450
max 2450

In [ ]: