dimanche 26 avril 2020

Python histogram of Randomized Quicksort Comparisons per Run

I have to implement the Las Vegas Randomized Quicksort algorithm and count the number of comparisons for each run to sort a random list of integers and create a histogram for the obtained valus with the number of runs being 10^4.

I am having trouble with the histogram, as it shows somethig this:

enter image description here

Instead of a distribution similar to this:

enter image description here

Here is the code I imagined. The number of comparisons is correct.

import random
import numpy as np
import matplotlib.pyplot as plt

def _inPlaceQuickSort(A, start, end):
    count = 0
    if start < end:
        pivot = randint(start, end)
        temp = A[end]
        A[end] = A[pivot]
        A[pivot] = temp

        p, count = _inPlacePartition(A, start, end)
        count += _inPlaceQuickSort(A, start, p - 1)
        count += _inPlaceQuickSort(A, p + 1, end)
    return count


def _inPlacePartition(A, start, end):

    count = 0
    pivot = randint(start, end)
    temp = A[end]
    A[end] = A[pivot]
    A[pivot] = temp
    newPivotIndex = start - 1
    for index in range(start, end):

        count += 1
        if A[index] < A[end]:  # check if current val is less than pivot value
            newPivotIndex = newPivotIndex + 1
            temp = A[newPivotIndex]
            A[newPivotIndex] = A[index]
            A[index] = temp

    temp = A[newPivotIndex + 1]
    A[newPivotIndex + 1] = A[end]
    A[end] = temp
    return newPivotIndex + 1, count 

if __name__ == "__main__": 
    for i in range(10):
        A={}
        for j in range(0, 10000):
            A[j] = random.randint(0, 10000)
        comp.append(_inPlaceQuickSort(A, 0, len(A) - 1)) 
    print(comp[i])

    plt.hist(comp, bins=50)
    plt.gca().set(title='|S|=10^4, Run=10^4', xlabel='Compares', ylabel='Frequency')



Aucun commentaire:

Enregistrer un commentaire