Sortowanie pozycyjne słów

W wypadku sortowania pozycyjnego słów, podobnie jak przy sortowaniu pozycyjnym dat i liczb, nie porównuje się ze sobą wartości wprost, tylko ich kolejne elementy składowe, zaczynając do najmniej znaczącego.

Przeanalizujmy przykład sortowania zbioru słów za pomocą algorytmu sortowania pozycyjnego. Naszym zadaniem jest uporządkowanie (od A do Z) następującego zbioru słów:

• DEC,

• DAC,

• CAD.

Zacznijmy od przypisania określonej liczby naturalnej każdej literze alfabetu łacińskiego. Liczby te będą pełniły rolę „odpowiedników”, za pomocą których określimy, czy dane dwie litery są na odpowiednich miejscach.

W przedstawionej tabeli kolejnym literom alfabetu łacińskiego przypisano kolejne liczby naturalne.

Następnie należy posortować słowa według kolejnych pozycji (wykorzystamy porządek leksykograficznyporządek leksykograficznyporządek leksykograficzny), zaczynając od pozycji najmniej znaczącej, za pomocą stabilnegoalgorytm stabilnystabilnego algorytmu sortowania, np. sortowania bąbelkowego, kubełkowego, przez wstawianie. Grafika przedstawia, jak wygląda zbiór po sortowaniach na kolejnych pozycjach. Kolorami oznaczono, według której pozycji odbywało się sortowanie.

R1JcHdB84HsQr

Ilustracja przedstawia cztery zbiory po trzy ciągli liter.
Od każdego zbiory wychodzi strzałka wskazująca na kolejny zbiór.
W pierwszym zbiorze litery nie są posortowane: DEC, DAC, CAD.
W drugim zbiorze posortowano alfabetycznie ciągi po ostatniej literze, które zaznaczono kolorem żółtym: DEC, DAC, CAD.
W trzecim zbiorze posortowano alfabetycznie ciągi po drugiej literze, które zaznaczono kolorem zielonym: DAC, CAD, DEC
W czwartym zbiorze posortowano ciągi po pierwszej literze, które zaznaczono kolorem czerwonym: CAD, DAC ,DEC
Ostatni zbiór tworzą posortowane alfabetycznie ciągi liter.

Przeanalizujmy powyższy przykład bardziej szczegółowo, a jako stabilny algorytm sortowania wybierzmy algorytm sortowania bąbelkowego.

Numery kolejnych pozycji (zaczynając od najmniej znaczącej) oznaczono kolejno 0, 1, 2:

R1D1RRAf9F5Ou

Ilustracja przedstawia ciąg liter: D, E, C.
Nad każdą literą znajduje się jej indeks: 0, 1, 2.

Dla pozycji 2:

REwfzCRwK3yyH

Ilustracja przedstawia trzy ciągli liter: DEC, DAC, CAD, ustawione jeden pod drugim.
Litery posiadają swoje indeksy, kolejno: 0, 1 , 2 .
Żółtym kolorem zaznaczono ostatnie litery ciągów z indeksami 2.

1. Czy 3 > 3? (C > C) – porównywane są wartości liczbowe przypisane do odpowiednich liter, ponieważ algorytm sortowania jest stabilny, nie następuje zamiana.

2. Czy 3 > 4? (C > D) – porównywane są kolejne liczby, jednak zamiana nie następuje, ponieważ chcemy posortować zbiór niemalejąco.

3. Po przejściu wszystkich liter na pozycji 2 nie nastąpiła zmiana, w związku z czym można zakończyć wykonywanie algorytmu sortowania bąbelkowego i przejść do pozycji nr 1.

Dla pozycji 1:

Rayw5BfT5dHvG

Ilustracja przedstawia trzy ciągli liter: DAC, CAD, DEC, ustawione jeden pod drugim.
Litery posiadają swoje indeksy, kolejno: 0, 1 , 2 .
Żółtym kolorem zaznaczono drugą literę ciągów z indeksem 1.

1. Czy 5 > 1? (E > A) – tak, wykonywana jest więc zamiana słów.

2. Czy 5 > 1? (E > A) – tak, wykonywana jest więc zamiana słów.

3. Po kolejnym przejściu wszystkich liter na pozycji 1 nie nastąpiła zmiana, w związku z czym można zakończyć wykonywanie algorytmu sortowania bąbelkowego i przejść do pozycji nr 0.

Dla pozycji 0:

Ry3GGFR4E1dvd

Ilustracja przedstawia trzy ciągli liter: CAD, DAC, DEC, ustawione jeden pod drugim.
Litery posiadają swoje indeksy, kolejno: 0, 1 , 2 .
Żółtym kolorem zaznaczono ostatnie litery ciągów o indeksie 0.

1. Czy 4 > 3? (D > C) – tak, następuje zamiana słów.

2. Czy 4 > 4? (D > D) – ponieważ algorytm sortowania jest stabilny, nie następuje zamiana.

3. Po przejściu wszystkich liter na pozycji 0 nie nastąpiła zmiana, w związku z czym można zakończyć wykonywanie algorytmu sortowania bąbelkowego i zakończyć algorytm.

Pseudokod

Podczas sortowania pozycyjnego zadanego zbioru słów postępujemy zgodnie z następującym algorytmem.

Specyfikacja:

Dane:

• Z – tablica słów długości n

• n – liczba naturalna; długość słów zawartych w tablicy Z

Wynik:

Funkcja zwraca posortowaną tablicę Z.

funkcja sortowaniePozycyjne(Z, n)
	dla i = n-1, n-2, ..., 0 wykonuj
    	posortuj stabilnie tablicę Z według znaków na pozycji i

W przedstawionym pseudokodzie zostało przyjęte, że każdy element ze zbioru Z składa się z n znaków. Pozycja 0 jest najbardziej znaczącą pozycją, natomiast pozycja n - 1 – najmniej znacząca.

Złożoność obliczeniowa

Sortowanie według kolejnych pozycji (liter) przeprowadzane jest w czasie liniowym O(n). Sortowanie wykonywane jest tyle razy, z ilu liter składają się słowa z danego zbioru.

Słownik