Метод Хоару быстрая сортировка С++
Нужно сортировать рандомно сгенерированные числа через очередь. Т.е рандомные числа заносятся в очередь, потом сортировка по 300 элементов. 1 "поток" - от 0 до 300, 2 "поток" от 300 до 600 и т.д всего 10 "потоков". Сортировка Хоару работает идеально. Получается разделить их на 300 элементов, но сортировка идет не правильно. Так же требуется подсчет времени сортировки каждого из "потоков". Голову уже сломал, информации нигде не нашел
#include <iostream>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <ctime>
#include "windows.h"
using namespace std;
void khoaraQuickSort(int* numbers, int left, int right)
{
int pivot;
int l_hold = left;
int r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
khoaraQuickSort(numbers, left, pivot - 1);
if (right > pivot)
khoaraQuickSort(numbers, pivot + 1, right);
}
int main()
{
setlocale(LC_ALL, "Russian");
int t_s, t_f;
queue<int> NumsToSort;
srand(time(NULL));
int ToSortNumbers[3000];
int N = 300;
for (int i = 0; i < 3000; i++) {
ToSortNumbers[i] = rand() % 999;
}
for (int i = 0; i < 10; i++) {
for (int z = N - 300; z < N; z++) {
cout << ToSortNumbers[i]<<" ";
}
t_s = GetTickCount();
khoaraQuickSort(ToSortNumbers, 0, 1000 - 1);
NumsToSort.push(ToSortNumbers[i]);
t_f = GetTickCount();
cout << endl<< "Номер сортировки: " << i + 1 << " Колличество отсортированных элементов: " << N << " Время сортировки (ms): " << t_f - t_s << " Колличество операций (N_op): " << endl; // Шаг в 300 элементов
N = N + 300;
}
}
Ответы (1 шт):
Автор решения: Павел Ериков
→ Ссылка
У тебя не правильно установлен индекс в строчке:
for (int z = N - 300; z < N; z++) {
cout << ToSortNumbers[i]<<" ";
}
Должно быть так:
for (int z = N - 300; z < N; z++) {
cout << ToSortNumbers[z]<<" "; // <---
}
- Расположение этого куска кода у тебя до сортировки, а должно быть после если ты хочешь видеть результат. Например после
t_f = GetTickCount(); - У тебя идет вызов функции с параметром
right = 1000 - 1, но у тебя 3000 элементов, а не 1000. Правильный код:khoaraQuickSort(ToSortNumbers, 0, 3000 - 1);
