Python 每个运行的随机快速排序比较直方图

Question

我必须实施 Las Vegas Randomized Quicksort 算法并计算每个运行的比较次数排序随机整数列表并为获得的值创建一个直方图，运行次数为 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 和@pjs 所指出的，您的问题是样本量，正如您在评论中提到的，如果您增加样本量，生成样本量将花费很多时间。

我的想法是用 C++ 软件生成数据（更快），然后用 Python 绘制它。有了它，我可以在不到 20 秒的时间内生成并绘制 10000 运行s。

这是我的代码（快速排序算法改编自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);
  }
}

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 << "/" << RUNS<< 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')

binCounts = [10, 50, 100, 200, 1000, 5000]

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

  plt.hist(vals, bins=binCount)
  plt.gca().set(title='|S|=10^4 | Runs=10^4', xlabel='Comparisons', ylabel='Runs')
  plt.savefig(f'out{binCount}.png')
  plt.close()

Python 每个运行的随机快速排序比较直方图

Python histogram of Randomized Quicksort Comparisons per Run

python

random

quicksort

Python 每个 运行 的随机快速排序比较直方图

Python histogram of Randomized Quicksort Comparisons per Run

python

random

quicksort

Python 每个运行的随机快速排序比较直方图