Witam,
Napisałem program sortujący, który ma zaimplementowane szybkie sortowanie oraz jako pivot wybiera ostatni element.
Jeżeli program sortuje 100.000.000 randomowych liczb to działa poprawnie, jeżeli sortuje 3000 malejąco ułożonych liczb to również działa poprawnie.
Problemy pojawiają się jeżeli chcę posortować np. 150.000.000 randomowych liczb lub 4000 malejąco ułożonych liczb.
Dodam jeszcze, że piszę w Visual Studio 2019.
Będę bardzo wdzięczny za jakąkolwiek pomoc lub wskazówkę.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void quickSort(long[], int);
void quickSortRecursion(long[], int, int);
int main() {
int n = 4000;
long* tab = new long[n];
for (int i = 0; i < n; i++) {
//tab[i] = rand()%2000000000;
tab[i] = n - i;
}
cout << "Start sort" << endl;
quickSort(tab, n);
return 0;
}
void quickSort(long tab[], int n) {
clock_t start = clock();
quickSortRecursion(tab, 0, n - 1);
cout << (clock() - start) / (double)CLOCKS_PER_SEC << "\n";
//for (int i = 0; i < n; i++) cout << tab[i] << " ";
}
void quickSortRecursion(long tab[], int indexPierwszy, int indexOstatni) {
if (indexPierwszy >= indexOstatni) return;
int indexA = indexPierwszy, indexB = indexPierwszy, valPivot = tab[indexOstatni];
for (indexA; indexA < indexOstatni; indexA++) {
if (tab[indexA] <= valPivot) {
int val = tab[indexA];
tab[indexA] = tab[indexB];
tab[indexB] = val;
indexB++;
}
}
tab[indexOstatni] = tab[indexB];
tab[indexB] = valPivot;
if (indexB > indexPierwszy) quickSortRecursion(tab, indexPierwszy, indexB - 1);
if (indexB < indexOstatni) quickSortRecursion(tab, indexB + 1, indexOstatni);
}
Pojawia się następujący błąd:
