Sortowanie Przez Wstrząsanie

Opis Algorytmu

Sortowanie Przez Wstrząsanie to algorytm, który porządkuje dane i jego zasada działania opiera się o algorytm Sortowania Bąbelkowego. W tym przypadku jednak nie przechodzi się po elementach tylko w jedną stronę, ale po dotarciu na koniec nieposortowanej części należy przejść do tyłu ponownie wykonując zamiany jeśli zajdzie taka potrzeba. W ten sposób większe oraz mniejsze elementy są coraz bliżej ich ostatecznego położenia.

Lista kroków

Przypuśćmy, że mamy daną tablicę tab o długości n. Wtedy, aby ją posortować należy:

1. Przypisz zakresowi [0, n - 1]
2. Sortuj kolejne pary od lewego zakresu do ostatniego zakresu
3. Zmniejsz prawy zakres
4. Sortuj kolejne pary od prawego zakresu do lewego
5. Zwiększ prawy zakres
6. Jeśli została wykonana jakakolwiek zamiana to wróć do punktu (2.)

Przykład

Weźmy listę L:={5, 2, 3, 6, 4, 1} kolejno będą wykonywane następujące porównania:

W powyższym schemacie porównywane elementy zostały na liście wyróżnione pogrubieniem, a elementy już na odpowiednim miejscu zostały zaznaczone zostały pochyleniem. Po wykonaniu wszystkich wymienionych kroków otrzymujemy posortowaną listę L:={1, 2, 3, 4, 5, 6}.

Złożoność

Szacuje się, że złożoność algorytmu Sortowania Przez Wstrząsanie jest lepsza niż w przypadku sortowania bąbelkowego, ale wciąż O(n²). Co wynika z faktu, że podczas każdego przejścia jest kolejno wykonywane n - 1 porównań, n - 2, .., 1. Najlepszy przypadek to O(n), który występuje gdy lista jest już posortowana. Złożoność pamięciowa rozwiązania wynosi O(1).

Implementacja

Funkcja sortuj() sortuje przekazaną tablicę tab zgodnie z ideą Sortowania Przez Wstrząsanie.

1. void sortuj(int* tab, int n) {
2.   int lewy = 0, prawy = n - 1;
3.   bool zamiana = true;
4.   while (zamiana == true) {
5.     zamiana = false;
6.     for (int i = lewy; i < prawy; i++) {
7.       if (tab[i] > tab[i + 1]) {
8.         swap(tab[i], tab[i + 1]);
9.         zamiana = true;
10.       }
11.     }
12.     prawy = prawy - 1;
13.     for (int i = prawy; i > lewy; i--) {
14.       if (tab[i] < tab[i - 1]) {
15.         swap(tab[i], tab[i - 1]);
16.         zamiana = true;
17.       }
18.     }
19.     lewy = lewy + 1;
20.   }
21. }

Na początek (2.) ustalamy, że cała tablica jest nie posortowana i (3.) deklarujemy zmienną zamiana - dzięki niej będzie można ograniczyć liczbę potrzebnych zamian. Następnie (4.) dopóki tablica nie jest posortowana to: (5. - 11.) sortujemy wszystkie pary elementów począwszy od pierwszego nieposortowanego i (12.) zmniejszamy prawy zakres, ponieważ na końcu jest już największy element (w nieposortowanej części tablicy). Następnie analogicznie wykonujemy (13. - 18.) sortowanie cofając się i (19.) zwiększamy lewy zakres. Jeśli został zamieniona chociaż jedna para elementów to zmianna zamiana ma wartość prawda. Wtedy należy jeszcze raz przejść przez listę, aby mieć pewność, że lista została posortowana.

Testowanie funkcji

Napisaną funkcję sortującą można przetestować poniższym kodem, który wczyta od użytkownika tablicę, a następnie ją posortuje rosnąco.

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

Napisz funkcję sortującą opartą na Sortowaniu Przez Wstrząsanie po wywołaniu której na liście bedą kolejno posortowane rosnąco wszystkie liczby parzyste, a następnie liczby nieparzyste. Przetestuj działanie funkcji dla różnych list.

Przykładowo napisana funkcja dla listy liczb: {5, 2, 1, 4, 3} wypisze na ekran:

1. 2, 4, 1, 5, 3

• Kod źródłowy Zadanie 1