Sortowanie (Nie)parzyste

Opis algorytmu

Zasada działania algorytmu sortowania Nieparzyste/Parzyste jest bardzo podobna do algorytmu sortowania bąbelkowego. W tym jednak przypadku staramy się ograniczyć potrzebne kroki do posortowania danych. W celu posortowania danych elementy są porównywane parami i jeśli nie spełniają warunku oczekiwanej zależności to są zamieniane. Zamienianie par odbywa się tyle razy jaką długość ma zadana tablica elementów. Jeśli numer powtórzenia pętli jest nieparzysty to zamieniane są kolejne pary bez pierwszego elementu. W iteracji parzystej pary są wybierane począwszy od pierwszego elementu. Zakładamy, że pierwsza iteracja ma numer 0.

Przykład 1

Jako przykład posortujmy L = {7, 3, 2, 6, 1, 8}. Rozpoczynamy sortowanie od wyboru par bez pierwszego elementu. Zakładamy, że lista ma zostać posortowana rosnąco, więc każda para musi spełniać zależność x_i < x_{i + 1}.

Oczywiście każda para może spełniać także warunek x_i > x_i + 1, aby dane były posortowane malejąco. Wszystko zależy jedynie od potrzeb oraz implementacji.

Przykład 1

Weźmy tym razem przykładowo listę L = {10, 6, 2, 3, 8, 1, 5, 7, 4, 9}. Ponownie tablica ma zostać posortowana rosnąco x_i < x_i + 1.

Implementacja

Zakładamy, że program ma do posortowania tablice liczb całkowitych tak, aby tablica była posortowana rosnąco. Zadanie można wykonać przy pomocy pętli for. W każdej iteracji rozpoznajemy jak mamy wybierać pary, a następnie to przeprowadzamy.

1. void sortuj(int* tab, int n) {
2.   for (int i = 0; i < n; i++) {
3.     if (i % 2 == 0) {
4.       for (int j = 1; j < n; j += 2) {
5.         if (tab[j] < tab[j - 1])
6.           swap(tab[j - 1], tab[j]);
7.       }
8.     } else {
9.       for (int j = 2; j < n; j += 2) {
10.         if (tab[j] < tab[j - 1])
11.           swap(tab[j - 1], tab[j]);
12.       }
13.     }
14.   }
15. }

(2.) Wykonujemy n iteracji. Za każdym razem (3.) sprawdzamy parzystość wykonywanej iteracji. Nastepnie (4. - 7.) sortujemy dane wybierając wszystkie pary po kolei, albo (9. - 12.) kolejne pary bez uwzględniania elementu pierwszego i ostatniego.

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika długość tablicy oraz jej elementy. Następnie sortuje dane i wypisuje posortowaną tablicę 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

Przepisz funkcję sortuj() tak, aby korzystała z rekurencji. Postaraj się tak napisać program, aby wewnątrz funkcji sortuj() występowała tylko jedna pętla z jednym warunkiem w środku. Przetestuj działanie funkcji.

• Kod źródłowy Zadanie 1