Sortowanie Pozycyjne

O sortowaniu

Sortowanie pozycyjne (ang. radix sort) jest stabilnym algorytmem sortowania. Dzięki niemu możemy posortować wyrażenia złożonych z dowolnych znaków. Sortowanie zaczynamy od znaków na pozycjach najmniej znaczących czyli od ostatnich znaków wyrażenia. Kolejny krok polega, aby posortować wyrażenia według przedostatniego znaku i tak kontynuujemy, aż dotrzemy do pierwszego znaku. Metoda ta znajduje zastosowanie podczas porządkowania bardzo dużych liczb. Załóżmy, że mamy n liczb po ponad kilka tysięcy cyfr. Liczby mogą się różnić tylko na ostatnich pozycjach. Próba sortowania tradycyjnymi metodami mogłaby się okazać nieefektywne ze względu na ilość wykonywanych porównań.

Algorytm sortujący według znaku jest dowolny. Możemy użyć tutaj algorytmu bąbelkowe o złożoności jak również sortowania szybkiego o złożoności algorytmu . W przypadku sortowania pozycyjnego złożoność wyniesie m*a, gdzie m określa ilu znakowe są porównywane elementy, a a to złożoność czasowa wybranego algorytmu sortowania.

Spróbujmy prześledzić teraz sortowanie na przykładzie listy L:={ACB, BAC, ABB}. Użyjemy do tego sortowania bąbelkowego. Pierwsze pętla będzie sortowała według ostatniego znaku każdego elementu.

(Pogrubione zostały znaki według których sortujemy, a kursywą zostały zapisane słowa porównywane)

Kolejną pętla sortuje według znaku na pozycji bardziej znaczącej - tutaj jest to drugi znak:

I ostatnia w tym przypadku iteracja, ponieważ długość wyrazów wynosi 3 to porządkowanie według pierwszego znaku:

W ten sposób uzyskaliśmy posortowaną rosnąco tablicę L:={ABB, ACB, BAC}.

Algorytm ten możemy stosować do sortowania wyrazów, bardzo długich liczb oraz list zawierający nietypowe obiekty tj. każdy element listy ma kilka pól. Algorytm sortowania pozycyjnego będzie można dostosować, aby można było sortować według wybranych pól. Najprostszym przykładem byłaby tu lista punktów. Sortowalibyśmy tutaj najpierw według współrzędnej Y, a potem po wartość współrzędnej X.

Implementacja

Załóżmy, że nasz program wczyta najpierw listę wyrazów długości d o n elementach. Na wyjście mamy zwrócić posortowaną listę elementów.

Ogólny przykład sortowania pozycyjnego wyglądałby tak:

1. void sort(char* list, int d, int n){
2.   for(int i = n - 1; i >= 0; i--){
3.     // tu wstawiamy dowolny algorytm sortujący
4.   }
5. }

Funkcję sortującą należy wstawić w linijce (3.). Algorytm sortujący powinien porównywać elementy według i-tego znaku wyrazów.

Uzupełniony algorytm sortowania pozycyjnego o sortowanie bąbelkowe wyglądałby tak:

1. void sort(char** list, int d, int n){
2.   char* temp = new char[d + 1];
3.   temp[d] = '\0';
4.   for(int i = d - 1; i >= 0; i--){
5.     for(int si = 0; si < n - 1; si++){
6.       for(int sj = 0; si + sj < n - 1; sj++){
7.         if(list[sj][i] > list[sj + 1][i]){
8.           strcpy(temp, list[sj]);
9.           strcpy(list[sj], list[sj + 1]);
10.           strcpy(list[sj + 1], temp);
11.         }
12.       }
13.     }
14.   }
15.   delete[] temp;
16. }

(1. - 2.) Do sortowania bąbelkowego będziemy potrzebować zmiennej tymczasowej, aby można było zamienić wartości miejscami. (4.) Dla kolejnych znaków - od najmniej do najbardziej znaczącego wykonujemy sortowanie bąbelkowe (5. - 13.) według i-tego co zostało zastosowane w linijce (7.) podczas porównywania elementów. (15.) Dealokujemy pamięć zarezerwowaną pod zmienną temp.

Testowanie funkcji

Funkcję sortującą możemy przetestować następującym kodem:

1. int main () {
2.   int d, n;
3.   cin >> d >> n;
4.   cin.sync();
5.   cin.clear();
6.   char** lista = new char*[n];
7.   for(int i = 0; i < n ; i++){
8.     char* t = new char[d + 1];
9.     cin.getline(t, d + 1);
10.     lista[i] = t;
11.   }
13.   sort(lista, d, n);
15.   for(int i = 0; i < n ; i++)
16.     cout << lista[i] << endl;
18.   for(int i = 0; i < n ; i++)
19.     delete[] lista[i];
20.   delete[] lista;
22.   system("pause");
23.   return 0;
24. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Zmodyfikuj funkcję sort(), aby dane były sortowane metodą Sortowania przez Wybór. Dane mają być posortowane malejąco.

Przykładowo dla danych:

1. 3 3
2. ACB
3. BAC
4. ABB

otrzymamy:

1. BAC
2. ACB
3. ABB

• Kod źródłowy Zadanie 1