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:
Instead of a distribution similar to this:
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