Dzielenie w czasie liniowym

Prawdziwa praca szybkiego sortowania dzieje się podczas kroku dzielenia, która dzieli pod-tablice array[p..r] wokół pivota zaczerpniętego z tej pod-tablicy. Mimo że możemy wybrać każdy element pod-tablicy jako pivot, najłatwiej jest zaimplementować dzielenie jeśli wybierzemy element najbardziej po prawej stronie tablicy A[r], jako pivot.

Po wybraniu pivota, dzielimy pod-tablice przechodząc z lewej do prawej, porównując każdy element z pivotem. Utrzymujemy dwa wskaźniki q i j w pod-tablicy, dzieląc ją na cztery grupy. Używamy zmiennej q, ponieważ będzie to ostatecznie index na nasz pivot. Używamy j, ponieważ jest to pospolita nawa na licznik oraz zostanie odrzucona, gdy skończymy.

Początkowo zarówno q i j są równe p. W każdym kroku porównujemy A[j], najbardziej lewy element w grupie U, z pivotem. Jeśli A[j] jest większy niż pivot, po prostu zwiększamy j, tak, aby linia podziału grupy G i U przeszła jedną pozycję w prawo:

Jeśli natomiast A[j] jest mniejsze lub równe pivotowi, wtedy zamieniamy A[j] i A[q] (element najbardziej lewy w grupie G), zwiększamy j oraz q, przesuwając linie dzielącą grupy L i G oraz grupy G i U jedną pozycję w prawo:

Kiedy dojdziemy do pivota, grupa U jest pusta. Zamieniamy pivot z pierwszym z lewej elementem w grupie G: zamieniamy A[r] i A[q]. Zamiana stawia pivot pomiędzy grupami L i G, działa to nawet wtedy kiedy grupa L albo G są puste. (Kiedy grupa L jest pusta, q nigdy nie wzrósł od początkowej wartości p, tak więc pivot przechodzi na lewy początek pod-tablicy. Jeśli grupa G jest pusta, q rośnie razem z j, kiedy j osiągnie index r pivota, q równa się r, zamiana zostawia pivot na prawym końcu pod-tablicy.) Funkcja dzieląca która realizuje ten pomysł zwraca index q, gdzie pivot ostatecznie skończył, tak aby funkcja quicksort, która ją wywołała, wiedział gdzie są poszczególne grupy. Tak wyglądają poszczególne kroki podczas dzielenia pod-tablicy [12, 7, 14, 9, 10, 11] w array[4.{,}9]:

Dzielenie pod-tablicy z $n$‍ elementów trwa $\mathrm{\Theta }(n)$‍. Każdy element A[j] jest porównywany raz pivotem. A[j] może lub nie być zamienione z A[q], q może lub nie być zwiększone, natomiast j jest zawsze zwiększane. Całkowita liczba wierszy na element pod-tablicy jest stała. Ponieważ pod-tablica ma $n$‍ elementów, czas podziału wynosi $\mathrm{\Theta }(n)$‍: proporcjonalna do ilości elementów.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.