Sortowanie Funkcją Skrótu

Wstęp

Sortowanie Funkcją Skrótu to propozycja algorytmu, który pozwala przyśpieszyć proces sortowania poprzez podzielenie sortowanej listy na mniejsze jej fragmenty poprzez zastosowanie funkcji skrótu. Powstałe części można posortować dowolnym innym algorytmem, albo kontynuować wykonywanie poprzez funkcję skrótu, ale wtedy dużo się traci na wydajności.

Algorytm

W celu podzielania tablicy na k części, które można posortować oddzielnie dzielimy zakres liczb tablicy tj. różnicę minimum i maksimum przez żądaną ilość części. Wynik zaokrąglamy w górę, aby mieć pewność, że wszystkie liczby znajdą się w pewnej grupie. Następnie skanujemy tablicę i wyznaczamy ile liczb należy do każdej grupy. Na podstawie tych informacji generowana jest tablica indeksów każdej grupy. Ostatni krok polega na przejrzeniu tablicy jeszcze raz, ale tym razem po wyliczeniu grupy pobieramy jej indeks i tam zapisujemy liczbę w tablicy wynikowej, a potem zwiększamy indeks. Każdy wyznaczony fragment należy posortować oddzielnie!

Grupę dla danej liczby wyznaczamy z funkcji skrótu. Dla dowolnej liczby n numer grupy to g = floor((n - min) / rozmiar_części), gdzie min to minimalna wartość w tablicy, a rozmiar_części = (max - min) / k.

Przykład

Sortujemy tablicę L = [1, 9, 2, 4, 8, 10, 6, 5, 0, 7]. Deklarujemy, że chcemy podzielić tablicę na k = 3 części. Pierwszy krok polega na wyznaczeniu zakresu wartości: min = 0, a max = 10. Z tego wynika, że rozmiar każdej części to ceil((10 - 0) / 3) = ceil(3.33..) = 4. Gdyby nie zaokrąglenie w górę to powstałaby 3 grupy po 3 elementy, a więc jeden byłby poza.

Pierwszy element to 1, a więc g = floor((1 - 0) / 4) = 0. Zwiększamy zatem liczebność grupy 0. Poniżej zostały podane liczby oraz ich przydział do grupy g:

Ostatecznie wiemy, że w grupie 0 są 3 elementy, w grupie 1 są 4 elementy, a w ostatniej 3. Teraz na podstawie tych informacji można zbudować tablice indeksów:

Teraz chcą zapisać liczbę 1 wyznaczamy g = 0. Pobieramy indeks grupy 0 czyli 0 i pod tym indeksem zapisujemy liczbę. Na koniec zwiększamy indeks. Poniżej został przedstawiony ten proces dla pozostałych liczb:

Ostatecznie sortowana tablica została podzielona na trzy części: [1, 2, 0], [4, 6, 5, 7], [9, 8, 10]. Każda z nich wymaga oddzielnego posortowania dowolną metodą.

Złożoność

Algorytm dla małych wartości nie pozwala przyśpieszyć sortowanie, ponieważ w celu podziału wymaga on, aż trzykrotnego przejrzenia tablicy. Niemniej warto pamiętać o tym, że dla sortowania bąbelkowego o złożoności O(n²) podział może dać znaczne przyśpieszenie. Przypuśćmy, że lista dzieli się na równej długości k części. Wtedy złożoność wyniesie O(k·(n/k)² = n²/k). Co ciekawe jeśli k = n to dane zostaną posortowane liniowo, ale pamiętajmy, że wtedy algorytm wymaga znacznie więcej dodatkowej pamięci. Należy pamiętać, że algorytm dzielenie wartości ma złożoność liniową O(n).

Implementacja

Poniżej został przedstawiony kod algorytmu, który sortuje przy użyciu sortowania funkcją skrótu. Przyjmuje on liczby do posortowania oraz żądaną ilość części k.

1. vector<int> SortujSkrotem(vector<int> liczby, int k) {
2.   int min = liczby[0];
3.   int max = liczby[0];
4.   for each (int x in liczby) {
5.     if (x < min) min = x;
6.     if (x > max) max = x;
7.   }
8.   int przedzial = (max - min + k - 1) / k;
9.   int* grupy = new int[k] {0};
10.   for each (int x in liczby) {
11.     grupy[Przydziel(x, min, przedzial)]++;
12.   }
13.   int* indeksy = new int[k] {0};
14.   for (int i = 1; i < k; i++) {
15.     indeksy[i] = indeksy[i - 1] + grupy[i - 1];
16.   }
17.   vector<int> wynik(liczby.size());
18.   for (int i = 0; i < liczby.size(); i++) {
19.     int grupa = Przydziel(liczby[i], min, przedzial);
20.     wynik[indeksy[grupa]] = liczby[i];
21.     indeksy[grupa]++;
22.   }
23.   int start = 0;
24.   for (int i = 0; i < k; i++) {
25.     sort(wynik.begin() + start, wynik.begin() + start + grupy[i]);
26.     start += grupy[i];
27.   }
28.   return wynik;
29. }

Na początku wyznaczone zostaną wartości minimum oraz maksimum. Kolejny krok to wyznaczenie ile liczb na leży do której grupy i na tej podstawie wyliczane są indeksy. Potem liczby zostają przepisane do swojej części tablicy. Ostatni krok to posortowanie każdej części oddzielnie.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego fragmentu programu.

1. int main() {
2.   int n, k, tmp;
3.   cout << "Ile liczb?\n n = ";
4.   cin >> n;
5.   cout << "Ile przedzialow?\n k = ";
6.   cin >> k;
7.   cout << "Podaj liczby:" << endl;
8.   vector<int> liczby;
9.   while (n-- > 0) {
10.     cin >> tmp;
11.     liczby.push_back(tmp);
12.   }
13.   vector<int> wynik = SortujSkrotem(liczby, k);
14.   cout << "Po posortowaniu:\n";
15.   for each (int x in wynik)
16.     cout << x << " ";
17.   system("pause");
18.   return 0;
19. }

• Kod źródłowy Implementacja