Sortowanie Cyklami

Opis

Algorytm Sortowania Cyklami to algorytm sortowania w miejscu w sposób niestabilny. Sortowanie odbywa się poprzez wybranie każdego kolejnego elementu, a następnie wstawienie go w odpowiednie miejsce, które możemy obliczyć wiedząc ile jest mniejszych elementów od niego. Zaletą tego algorytmu jest fakt, że każdy element jest nadpisywany maksymalnie raz, więc jest on przydatny wszędzie tam gdzie zapis jest kosztowny.

Lista kroków

Dla każdego kolejnego elementu wyliczamy ile jest na liście elementów mniejszych od niego. Jeśli wyliczona pozycja jest taka sama jak ta na której element się znajduje to nic nie robimy. W przeciwnym razie wstawiamy w odpowiednie miejsce, a dla nadpisanego elementu szukamy jego właściwej pozycji.

Przykład

Weźmy przykładowo tablice L := {5, 1, 4, 3, 2}. Wykonane zostaną kolejne kroki:

Złożoność

Zauważmy, że niezależnie od tego jak wygląda lista to dla każdego z n elementów wykonujemy dokładnie n - 1 porównań, więc zawsze gwarantowane jest, że operacji będzie n² z czego wynika złożoność O(n²). Dodatkowo warto zauważyć, że algorytm wymaga jedynie zapamiętania poza tablicą pojedynczego elementu, więc złożoność pamięciowa wynosi O(1). Warto oczywiście dodatkowo pamiętać, że każdy element może zostać napisany maksymalnie raz, więc maksymalna ilość zapisów wynosi n. Większość algorytmów poprzez stosowanie zamian elementów potrzebuje o wiele więcej zamian.

Implementacja

Funkcja sortuj() sortuje podane dane w tablicy w miejscu zgodnie z algorytmem Sortowania Cyklami.

1.   for (int i = 0; i < n - 1; i++) {
2.     int item = tab[i];
3.     int pos = i;
4.     for (int j = i + 1; j < n; j++)
5.       if (tab[j] < item)
6.         pos++;
7.     if (pos == i)
8.       continue;
9.     while (item == tab[pos])
10.       pos++;
11.     swap(tab[pos], item);
12.     while (pos != i) {
13.       pos = i;
14.       for (int j = i + 1; j < n; j++)
15.         if (tab[j] < item)
16.           pos++;
17.       while (item == tab[pos])
18.         pos++;
19.       swap(tab[pos], item);
20.     }
21.   }
22. }

(2.) Dla każdego elementu w tablicy (prócz ostatniego, bo nie ma takiej potrzeby): (3.) zapamiętujemy element, (4.) przyjmujemy, że jest na prawidłowej pozycji. Dalej (5. - 7.) weryfikujemy to poprzez aktualizację jego pozycji. (8.) Jeśli mimo wszystko jest na swojej pozycji to (9.) przechodzimy do następnej iteracji, ale jeśli nie to musimy ten element przestawić. W celu wstawienia (10. - 11.) sprawdzamy czy na miejscu do wstawienia nie ma już danego elementu - jeśli jest to zwiększamy numer pozycji, a potem (12.) zamieniamy przestawiany element z elementem na danej pozycji. Potem (13. - 21.) powtarzamy proces wstawiania dla każdego kolejnego elementu, aż nie wrócimy pod indeks z którego rozpoczął się cykl zamiany.

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika długość tablicy oraz jej elementy, a następnie ją sortuje i wypisuje na ekran.

1. int main() {
2.   int n;
3.   cout << "Podaj ile jest elementow\n n = ";
4.   cin >> n;
5.   int* tab = new int[n];
6.   cout << "Podaj elementy:\n";
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   sortuj(tab, n);
10.   cout << "Po posortowaniu:\n";
11.   for (int i = 0; i < n; i++)
12.     cout << tab[i] << " ";
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Sprawdź dla wszystkich permutacji ciągu o długości n ile jest potrzebnych operacji nadpisania elementów w tablicy na przykładzie Sortowania Cyklami oraz Sortowania Przez Wybór. Przetestuj działanie funkcji na wybranych danych. Pamiętaj, że zliczane mają być wszystkie zapisy do tablicy!

Przykładowo dla permutacji 5 elementów program (w zależności od implementacji algorytmów) może wypisać:

1. Sortowanie     Zapisow
2. Cyklami        480
3. Przez Wybór    652

• Kod źródłowy Zadanie 1