Strona główna » Algorytmy » Sortowanie » Sortowanie (Nie)parzyste
 

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ść xi < xi + 1.

Iteracja 0732618
Iteracja 1372618
Iteracja 2327168
Iteracja 3231768
Iteracja 4213678
Ostatecznie123678

Oczywiście każda para może spełniać także warunek xi > xi + 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 xi < xi + 1.

Iteracja 010623815749
Iteracja 161023185749
Iteracja 262101358479
Iteracja 326110354879
Iteracja 421631045789
Iteracja 512364105789
Iteracja 612346510789
Iteracja 712345671089
Iteracja 812345678109
Ostatecznie12345678910

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.

C++
C#
  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.

C++
C#
  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. }

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.