Python гистограмма рандомизированных сравнений быстрой сортировки за цикл - PullRequest
Новая
       29

Python гистограмма рандомизированных сравнений быстрой сортировки за цикл

0 голосов
/ 26 апреля 2020

Мне нужно реализовать алгоритм рандомизированной быстрой сортировки в Лас-Вегасе и подсчитать количество сравнений для каждого прогона, чтобы отсортировать случайный список целых чисел, и создать гистограмму для полученного значения с числом прогонов, равным 10 ^ 4.

У меня проблемы с гистограммой, так как она показывает следующее:

enter image description here

Вместо распределения, подобного этому:

enter image description here

Вот код, который я себе представил. Количество сравнений правильное. 

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')

Ответы [ 2 ]

1 голос
/ 27 апреля 2020

Как отметили @Tom De Coninck и @ p js, ваша проблема в размере выборки, и, как вы упомянули в комментарии, если вы увеличите размер выборки, для ее генерации потребуется много времени.

Моя идея заключается в том, чтобы сгенерировать данные с помощью программного обеспечения C ++ (намного быстрее), а затем построить их с помощью Python. С этим я могу сгенерировать и построить 10000 запусков менее чем за 20 секунд.

Вот мой код (алгоритм быстрой сортировки был адаптирован из C ++ Программа для быстрой сортировки - 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()
1 голос
/ 27 апреля 2020

Вы добавляете что-то в свою переменную Comp в 10 раз, и ваш вывод показывает график с 10 значениями в гистограмме.

Если вы хотите что-то большее в предоставленном распределении, вы должны увеличить диапазон в вашем I например, для l oop до 1000.

...