10 kwietnia 2014

Algorytm sortowania quicksort ze stanem

Algorytm sortowania szybkiego ma kilka kiepskich przypadków. Należy do nich już posortowana tablica (P. Wróblewski, Algorytmy, struktury danych i techniki programowania).
Wykorzystując tablicę stanów można tak zmodyfikować ten algorytm, że łączna krotność zamian elementów może sie zbliżyć do sortowania przez selekcję. Zaś sortowanie przez selekcję ma najmniejszą możliwą liczność zamian (R. Sedgewick, Algorytmy w C++). Ta wersja quicksortu nie zawsze osiągnie tę granicę, lecz liczność zmian mocno się zmniejsza.

Algorytm  quicksort dzieli tablicę na trzy części. Pobiera jeden z elementów oraz szuka dla niego docelowego miejsca w tablicy. Elementy poprzedzające są mniejsze niż rozpatrywany, następne są większe. Następnie quicksort wywołuje sam siebie ponownie dla tych części.

Moja modyfikacja sprawdza, czy tablica nie jest już posortowana. Dla wybranego elementu sprawdza, czy nie ma przypadkiem wartości równych danej.
Wprowadzam funkcję, która dla zadanej wartości zwraca funktor <, = albo >, związany ze stanem. Parametrem funktora jest element tablicy. Ponowne wywołanie tej funkcji usuwa funktor wydobywając zawartość - sortowany element.
Oczywiście dla tablicy długości poniżej 3 elementów użycie funktora jest niepotrzebne - sortowanie następuje od razu. 

Oto stany algorytmu quicksort oraz ich interpretacja:
1 - wszystkie elementy są równe,
2 - elementy tablicy tworzą ciąg niemalejący, porównanie jest z elementem poprzedzającym, nie z wybranym,
3 - elementy tablicy tworzą ciąg nierosnący, porównanie jest z elementem następnym, nie z wybranym,
4 - elementy tablicy nie są posortowane, oraz począwszy od pewnego miejsca nie ma elementów równych,  porównanie z elementem wybranym,
5 - elementy tablicy nie są posortowane, występują elementy równe elementowi aktualnie rozpatrywanemu, porównanie z elementem wybranym.

Dla pierwszych trzech stanów, wystarczy do jednego liniowego przejścia, by mieć posortowaną tablicę. Przerobienie tablicy w stanie 3 na listę posortowaną rosnącą wymaga użycia funkcji reverse, odwracajacej kolejność tablicy.
Stan czwarty odpowiada standardowemu podejściu do quicksort. Natomiast stan 5 wymaga dodatkowego przejścia zcalającego elementy równe sobie, też złożoności liniowej.   

Tablica stanów, kiedy porównanie dwu elementów a, b zwraca relację <, =, >. Funktor > jest zwracany, jeśli bieżący element jest większy niż porównywany lub równy w stanie 2, funktor < dla elementu mniejszego lub równego w stanie 3.
Stan  <    =    >, drugi z symboli to wartość (funktor)
1       3<  1=  2>
2       ?     2>  2>
3       3<  3<  ?
4       4<  5=  4>
5       5<  5=  5>
Obszary oznaczone pytajnikiem są oprócz zmiany stanu na 4 albo 5 są  powieleniem porównania, raz dla elementu poprzedzajacego, docelowo dla wybranego. Jeśli w ciagu słabo rosnącym jest element mniejszy od przedostatniego, lecz większy od wybranego, następuje zwrot funktora >, dla równego elementowi wybranemu zwrot funktora =. Jeśli porównywany element jest mniejszy zarówno od elementu poprzedzającego, jak i od wybranego, zwracany jest funktor <. Podobna sytuacja występuje dla ciągu słabo malejącego, wartość i stan jest nadawana w zależności od drugiego porównania.
Teraz w tabeli mamy ciąg funktorów. Jeśli mamy stan 5, blokujemy ponowne wywołanie funkcji do następnego przejścia. Teraz poruszając się od krańców tablicy zamieniamy ze sobą funktory > z początku tablicy oraz < z końca tablicy. W stanie 4 od razu od razu stosujemy ponownie funkcję, by odzyskać wartości elementów. Ostatnim krokiem jest zamiana elementu wybranego z ostatnim elementem o wartości <, wskazywanym indeksem, który służy do podziału tablicy do kolejnych iteracji.
W stanie 5 należy jeszcze raz przejść tablicę wymieniając elementy oznaczone relacją = z przyległymi do docelowego miejsca, modyfikując zakres tablicy. Elementy w środkowej części tablicy są wtedy na swoich miejscach i nie będą dalej ruszane.
Mamy tablicę, w której element wybrany jest na docelowej pozycji, mniejsze go poprzedzają, większe następują po rozpatrywanym elemencie.
Następuje wywołanie rekursywne dla obu części.

Przykład:
A S O R T I N G E X A M P L E
pierwszym, porównywanym elementem jest A, porównujemy w stanie 1:
S>A, stan 2, zwracamy >,
O<S, porównujemy O>A, stan 4, zwracamy >,
R>A, zwrot >
jeszcze parę wyrazów
A=A, stan 5, zwrot =
dokańczając porównania uzyskujemy tablicę w stanie 5
= > > > > > > > > > = > > > >
wyszukanie relacji < daje wartość pustą, zcalamy wartości z relacją = stosując funkcję. Uzyskujemy tablicę (jedna zamiana), z której można odciąć jeszcze jeden element A:
A | A O R T I N G E X S M P L E
wywołujemy quicksort ponownie. Po jednej stronie ciąg pusty czyli nie ma co robić, po drugiej
O R T I N G E X S M P L E
porównujemy w stanie 1:
R>O, stan 2, zwrot >
T>R, zwrot >
I<T, porównujemy I<O, stan 4, zwrot <
N<O, zwrot <
G<O, zwrot <
E<O, zwrot <
X>O, zwrot >
S>O, zwrot >
M<O, zwrot <
P>O, zwrot >
L<O, zwrot <
E<O, zwrot <
nowa tablica w stanie 4
= > > < < < < > > < > < <
zamieniamy ze sobą skrajne relacje (>,<) czyli: (R,E), (T,L), (X,M) uzyskując
O E L I N G E M | S X P T R
ostatnia zamiana elementów (O,M)
M E L I N G E | O | S X P T R
oraz ponowne wywołanie dla MELINGE oraz SXPTR itd.