Sortowanie introspektywne — część 5

Dzięki temu dla danych losowych sortowanie introspektywne będzie działało tak samo jak sortowanie szybkie z odcinaniem małych podzbiorów, a sortowanie przez kopcowanie jako sortowanie pomocnicze wywoływane będzie tylko wówczas, gdy przynajmniej początkowe podziały będą zdegenerowane.

Listing procedury hybrydowego sortowania introspektywnego w języku C++ template <class Item> void Hybrid_Introspective_Sort(Item* Array, long N) { IntroSort(Array, N, (int)floor(2 * log(N) / M_LN2)); Insertion_Sort(Array, N); }

template <class Item> void IntroSort(Item* Array, long N, int M) { if (M <= 0)

Heap_Sort(Array, N); return;

long i = Partition(Array, 0, N); if (i > 9) IntroSort(Array, i, M - 1); if (N - 1 - i > 9) IntroSort(Array + i + 1, N - 1 - i, M - 1); }

Kod procedury Partition jest taki sam, jak w przypadku sortowania szybkiego: template <class Item> long Partition(Item* Array, long L, long R) { if (R >= 3) Median_Of_Three(Array, L, R); long i = L; long j = R - 2; while (true)

while (Array[i]<Array[R - 1]) ++i; while (j >= L && Array[j] > Array[R - 1]) --j; if (i < j) Exchange(Array, i++, j--); else break;

Exchange(Array, i, R - 1); return i; }