Метод Хоару быстрая сортировка С++

187
22 апреля 2022, 04:20

Нужно сортировать рандомно сгенерированные числа через очередь. Т.е рандомные числа заносятся в очередь, потом сортировка по 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;
    }
}

Answer 1

У тебя не правильно установлен индекс в строчке:

for (int z = N - 300; z < N; z++) {
    cout << ToSortNumbers[i]<<" ";
}

Должно быть так:

for (int z = N - 300; z < N; z++) {
    cout << ToSortNumbers[z]<<" "; // <---
}
  1. Расположение этого куска кода у тебя до сортировки, а должно быть после если ты хочешь видеть результат. Например после t_f = GetTickCount();
  2. У тебя идет вызов функции с параметром right = 1000 - 1, но у тебя 3000 элементов, а не 1000. Правильный код: khoaraQuickSort(ToSortNumbers, 0, 3000 - 1);
READ ALSO
Написать формулу по вычислению площади многоугольника с определенным рядом условий

Написать формулу по вычислению площади многоугольника с определенным рядом условий

Я новичок в плюсахВводится количество вершин многоугольника

163
С++, матрица, задача

С++, матрица, задача

Помогите, пожалуйста, создать программу на базе с++Разбираюсь второй день - уже голова от этих матриц болит

172
C++. Простая задача

C++. Простая задача

Задача: Составить алгоритм увеличения всех трех, введённых с клавиатуры, переменных на 5,если среди них есть хотя бы две равныеВ противном...

124
Небольшая проблема с выравниванием чисел по правому краю. C++

Небольшая проблема с выравниванием чисел по правому краю. C++

У меня есть последовательность чисел, которая разбивается на строкиКол-во строк зависит от кол-ва чисел(выбирается рандомно в диапазоне...

121