Я пытаюсь измерить длительность функций сортировки слиянием и быстрой сортировки, используя вычисления времени std :: chrono и используя случайно сгенерированные массивы целых чисел в некотором диапазоне [A, B], размеры массивов варьируются от 5000 до100 000 целых чисел.
Цель моего кода - доказать, что когда метод выбора (сводной) в быстрой сортировке улучшается, функция быстрой сортировки в конечном итоге занимает меньше времени для обработки массива, чем сортировка слиянием,способ, которым я выбираю сводку, использует метод случайного индекса, чтобы минимизировать вероятность наличия сложности (n ^ 2). Однако в некоторых случаях, которые я опишу ниже, быстрая сортировка заканчивается больше времени, чем сортировка слиянием, и яхотел бы знать, почему это происходит.
case 1: диапазон чисел в массиве мал, что увеличивает вероятность наличия дублирующихся чисел в массиве.
case 2: когда Iиспользуйте локальную среду разработки, например clion, функция быстрой сортировки занимает намного больше времени, чем сортировка слиянием, однакоНесмотря на то, что компилятор, такой как IDEONE.com, дает одинаковые результаты в обоих алгоритмах сортировки (даже когда диапазон генерируемых целых чисел мал)
вот результаты, которые я получил в упомянутых случаях (первая строка чисел - сортировка слияниемРезультаты, вторая строка результатов быстрой сортировки):
Результаты 1-clion узкий диапазон чисел (-100, 600) 
Результаты 2-clion с широким диапазоном чисел(INT_MIN, INT_MAX) 
3-IDEONE результаты с узким диапазоном чисел (-100, 600) 
4-IDEONE результаты с широким диапазоном чисел (INT_MIN, INT_MAX) 
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int* generateArray(int size)
{
int* arr = new int[size];
uniform_int_distribution<> distribution(INT_MIN, INT_MAX);
for (int i=0; i < size; ++i)
{
arr[i] = distribution(gen);
}
return arr;
}
void merge(int* leftArr, int nL, int* rightArr, int nR, int* mainArr)
{
int i=0, j=0, k=0;
while (i < nL && j < nR)
{
if (leftArr[i] < rightArr[j]) { mainArr[k++] = leftArr[i++]; }
else { mainArr[k++] = rightArr[j++]; }
}
while (i < nL){ mainArr[k++] = leftArr[i++]; }
while (j < nR){ mainArr[k++] = rightArr[j++]; }
}
void mergeSort (int* mainArray, int arrayLength)
{
if (arrayLength < 2) { return; }
int mid = arrayLength/2;
int* leftArray = new int[mid];
int* rightArray = new int[arrayLength - mid];
for (int i=0; i<mid; ++i) {leftArray[i] = mainArray[i];}
for (int i = mid; i<arrayLength; ++i) {rightArray[i - mid] = mainArray[i];}
mergeSort(leftArray, mid);
mergeSort(rightArray, arrayLength-mid);
merge(leftArray, mid, rightArray, arrayLength-mid, mainArray);
delete[] leftArray;
delete[] rightArray;
}
int partition (int* arr, int left, int right)
{
uniform_int_distribution<> distribution(left, right);
int idx = distribution(gen);
swap(arr[right], arr[idx]);
int pivot = arr[right];
int partitionIndex = left;
for (int i = left; i < right; ++i)
{
if (arr[i] <= pivot)
{
swap(arr[i], arr[partitionIndex]);
partitionIndex++;
}
}
swap(arr[right], arr[partitionIndex]);
return partitionIndex;
}
void quickSort (int* arr, int left, int right)
{
if(left < right)
{
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
}
int main()
{
vector <long long> mergeDuration;
vector <long long> quickDuration;
for (int i = 5000; i<= 100000; i += 5000)
{
int* arr = generateArray(i);
auto startTime = chrono::high_resolution_clock::now();
quickSort(arr, 0, i - 1);
auto endTime = chrono::high_resolution_clock::now();
long long duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
quickDuration.push_back(duration);
delete[] arr;
}
for (int i = 5000; i <= 100000; i += 5000 )
{
int* arr = generateArray(i);
auto startTime = chrono::high_resolution_clock::now();
mergeSort(arr, i);
auto endTime = chrono::high_resolution_clock::now();
long long duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
mergeDuration.push_back(duration);
delete[] arr;
}
for (int i = 0; i<mergeDuration.size(); ++i)
{
cout << mergeDuration[i] << " ";
}
cout << endl;
for (int i = 0; i<quickDuration.size(); ++i)
{
cout << quickDuration[i] << " ";
}
}