每次运行随机化Quicksort比较的Python直方图

Question

我必须实现拉斯维加斯随机快速排序算法，并计算每次运行的比较次数，以对随机整数列表进行排序，并为获得的值创建直方图，运行次数为10 ^ 4。

我在使用直方图时遇到麻烦，因为它显示了一些东西：

代替与此类似的分布：

这是我想象中的代码。比较次数是正确的。

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__": 
    comp = []
    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')

Answer 1

您向变量Comp添加了10倍，输出显示了一个在直方图中具有10个值的图形。

如果您希望对所提供的分布有更多了解，则应将I for循环的范围增加到例如1000。

Answer 2

正如@Tom De Coninck指出的那样，您的问题是样本大小，并且，正如您在评论中提到的，如果您增加样本大小，则将花费大量时间来生成它。

我的想法是使用C ++软件（快得多）生成数据，然后使用Python进行绘制。这样，我可以在不到20秒的时间内生成并绘制10000次运行。

这是我的代码（快速排序算法改编自C++ Program for QuickSort - GeeksforGeeks）

C ++代码生成out.txt，其中包含用换行符分隔的每次运行的比较总数。 Python脚本读取线条并将其绘制（具有各种存储桶大小，作为分配状态）

C ++生成器

// g++ ./LVQuickSort.cpp -o lvquicksort

#include <iostream>
#include <fstream>
#include <cstdlib>

int ARRAY_TO_SORT_SIZE = 10000;
int RUNS = 10000;

void swap(int *a, int *b)
{
  int t = *a;
  *a = *b;
  *b = t;
}

int partition(int arr[], int low, int high, int &comps)
{
  int pivot = arr[(rand() % (high - low)) + low];
  int i = (low - 1);

  for (int j = low; j <= high - 1; j++)
  {
    comps++;
    if (arr[j] <= pivot)
    {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return (i + 1);
}

void quickSort(int arr[], int low, int high, int &comps)
{
  if (low < high)
  {
    int pi = partition(arr, low, high, comps);

    quickSort(arr, low, pi - 1, comps);
    quickSort(arr, pi + 1, high, comps);
  }
}

void printArray(int arr[], int size)
{
  int i;
  for (i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("n");
}

std::ofstream file;

void write_comps_to_file(int comps)
{
  file << comps << std::endl;
}

int main()
{
  file.open("./out.txt", std::fstream::trunc);

  for (size_t i = 0; i < RUNS; i++)
  {
    int *arr = (int *)malloc(sizeof(int) * ARRAY_TO_SORT_SIZE);
    for (int i = 0; i < ARRAY_TO_SORT_SIZE; i++)
      arr[i] = rand() % 1000;

    int comps = 0;

    if (i % (RUNS / 50) == 0)
      std::cout << i << "/" << ARRAY_TO_SORT_SIZE << std::endl;

    quickSort(arr, 0, ARRAY_TO_SORT_SIZE - 1, comps);
    write_comps_to_file(comps);
  }

  file.close();
}

Python绘图仪

import matplotlib.pyplot as plt

f = open('out.txt', 'r')

binSizes = [10, 50, 200, 1000]

for binSize in binSizes:
  vals = []
  f.seek(0)
  for line in f.readlines():
    vals.append(int(line))

  _ = plt.hist(vals, bins=binSize)
  plt.title(f"Histogram with bin size = {binSize}")
  plt.savefig(f'out{binSize}.png')
  plt.close()