QuickSort

Witam, mam pewien problem z quicksortem, który dla wylosowanej tablicy działa super przy każdym jej rozmiarze. Problem pojawia się gdy chcę zadziałać quicksortem na posortowaną tablicę i obliczyć liczbę przestawień. Dla rozmiaru tablicy około 3000 działa jednak dla większych rozmiarów pojawia się stack overflow. Byłbym wdzięczny za pomoc, bo nie mam pomysłu z czego to wynika. Problem pojawia się zarówno dla wersji Lomuto jak i Hoare.

int Lomuto_Quicksort(int* Tab, int low, int top, int &numberOfComparisons, int &numberOfInversions)
{
	if (low >= top) return 0;

	int pivot = Tab[top];
	int b = low;
	for (int a = low; a < top; a++)
	{
		numberOfComparisons++;

		if (Tab[a] <= pivot)
		{
			swap(Tab[a], Tab[b]);
			numberOfInversions++;
			b++;
		}
	}

	swap(Tab[b], Tab[top]);
	numberOfInversions++;

	Lomuto_Quicksort(Tab, low, b - 1, numberOfComparisons, numberOfInversions);
	Lomuto_Quicksort(Tab, b + 1, top, numberOfComparisons, numberOfInversions);
}

int Hoare_Quicksort(int* Tab, int low, int top, int& numberOfComparisons, int& numberOfInversions)
{
	if (low >= top) return 0;

	int piwot = Tab[low];
	int i = low;
	int j = top;

	while (i <= j)
	{
		while (Tab[i] < piwot)
		{
			numberOfComparisons++;
			i++;
		}

		while (Tab[j] > piwot)
		{
			numberOfComparisons++;
			j--;
		}

		if (i <= j)
		{
			numberOfInversions++;
			swap(Tab[i], Tab[j]);
			i++;
			j--;
		}
	}

	Hoare_Quicksort(Tab, low, j, numberOfComparisons, numberOfInversions);
	Hoare_Quicksort(Tab, i, top, numberOfComparisons, numberOfInversions);
}

Dałem mu posortowaną tablicę o stu tysiącach elementów i po chwili wyliczył; wyniki są dziewięciocyfrowe, to by się zgadzało, bo złożoność jest kwadratowa. Coś Musisz mieć mało pamięci, albo jakieś ustawienia skopane (za mały stos).

Tablica posortowana (albo odwrotnie posortowana) to “worst case” przy naiwnym wyborze pivota.
Spróbuj zastosować np. median of three, czyli element o środkowej wartości z trzech: pierwszego, środkowego i ostatniego.
Istnieje co prawda też sekwencja “median of three killer” i tak powoli zbliżamy się w stronę introsorta…

Tak, tak, ale jemu się gdzieś stos przepełnia z jakiś powodów.