Sortowanie Naleśnikowe

Problem

W celu zrozumienia na czym polega Sortowanie Naleśnikowe należy przyjrzeć się procesowi smażenia naleśników. Zazwyczaj każdego robi się oddzielnie wypełniając masą całą powierzchnię patelni tak, aby były jak największe. Oznacza to jednak, że po przygotowaniu naleśnik trafia na pewien stos, aż wszystkie naleśniki zostaną zrobione. Pomimo szczerych chęci naleśniki nie zawsze wychodzą takiego samego rozmiaru.

W celu posortowania naleśników tak, aby na dole były największe, a u góry największe można posłużyć się łopatką. W tym celu wybieramy naleśnik pod który podkładamy łopatkę, a następnie obracamy cały stos na łopatce do góry nogami. Kontynuując ten proces dochodzimy do momentu, gdy stos zostanie posortowany. Jednak jak się zabrać za tego typu sortowanie?

Technika

Rozpocznijmy od najprostszych przypadków. Jednego naleśnika nie ma co sortować, a w przypadku dwóch wystarczy odwrócić kolejność. Problem jednak się zaczyna dla trzech. Jeśli największy naleśnik jest na wierzchu to wystarczy odwrócić stos i znajdzie się na dole, a pozostałe dwa ewentualnie ponownie obrócić. Jednak jeśli nie znajduje się na wierzchu to można odwrócić fragment stosu tak, aby się na wierzchu znalazł.

Zasadę tę można przenieść na stosy o większej ilości naleśników. Po ułożeniu największego naleśnika na dole można rozpatrywać sortowanie stosu o jeden element mniejszego. Warto tutaj zauważyć, że implementacja rekurencyjnego sortowania będzie pasować idealnie.

Sortowanie

Poniżej został przedstawiony problem sortowania naleśników ułożonych na stosie (od dołu) kolejno: 3, 4, 1, 2. Najpierw znajdujemy największy naleśnik i przerzucamy go na górę stosu.

Teraz bardzo łatwo można go przerzucić na dół stosu - wystarczy obrócić cały stos do góry nogami. W tym celu wkładamy łopatkę pod cały stos.

Największy naleśnik jest już na miejscu, więc rozpatrujemy stos o jeden naleśnik mniejszy. Największy z nich leży na wierzchu, więc wkładamy szpatułkę nad ustawiony wcześniej element.

Stos został posortowany. Program jeszcze by dodatkowo posortował dwa naleśniki z wierzchu (tj. tylko sprawdził czy są posortowane).

Co można przedstawić schematycznie w postaci tabeli:

Implementacja

W celu zaimplementowanie tego algorytmu potrzebne są funkcje do: wyszukiwania elementu maksymalnego oraz do obracania wszystkich elementów począwszy od pewnego indeksu.

Wyszukiwanie maksimum

Funkcja wyszukajMaksimum() wyszukuje w pewnej tablicy tab o długości n największą wartość od indeksu i. Funkcja zwraca pozycję takiego elementu.

1. int wyszukajMaksimum(double* tab, int n, int i = 0) {
2.   int poz = i;
3.   for (i++; i < n; i++) {
4.     if (tab[i] > tab[poz]) {
5.       poz = i;
6.     }
7.   }
8.   return poz;
9. }

Odwracanie

Warto zauważyć, że w celu odwrócenia n elementów trzeba wykonać maksymalnie n/2 zamian, ponieważ za każdym razem zmieniamy wartości na skraju i zwężamy przedział o jeden z każdej strony.

Taką funkcjonalność implementuje funkcja odwroc(), która odwraca w tablicy tab o długości n elementy od indeksu i do ostatniego.

1. void odwroc(double* tab, int n, int i = 0) {
2.   for (n--; i < n; i++, n--)
3.     swap(tab[i], tab[n]);
4. }

Funkcja główna

Funkcja sortowanieNalesnikowe() przyjmuje do posortwania tablicę tab o n elementach.

1. void sortowanieNalesnikowe(double* tab, int n) {
2.   if (n <= 1) return;
3.   for (int i = 0; i + 1 < n; i++) {
4.     int poz = wyszukajMaksimum(tab, n, i);
5.     if (poz != n - 1)
6.       odwroc(tab, n, poz);
7.     odwroc(tab, n, i);
8.   }
9. }

(2.) Pomijamy przypadek trywialny, a następnie (3.) w pętli do posortowania n - 1 elementów w każdej iteracji (4.) wyszukujemy elementu największego. Jeśli (5.) największy naleśnik nie leży na wierzchu to (6.) ustaw go tam, a następnie (7.) przestaw go na dół stosu.

Testowanie programu

Program można przetestować poniższym fragmentem kodu:

1. int main () {
2.   int n;
3.   cout << "Podaj ile jest nalesnikow\nn = ";
4.   cin >> n;
5.   double* tab = new double[n];
6.   cout << "Podaj wielkosci nalesnikow, poczawszy od polozonego najnizej:\n";
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   sortowanieNalesnikowe(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 program, który będzie sortował naleśniki tak, aby namniejszy znalazł się na dole stosu. Uwaga: nie wolno na koniec sortowania odwrócić całego stosu, aby posortować malejąco.

Przykładowo dla stosu (od dołu): {5, 3, 1, 2, 4} program powinien zwrócić:

5 4 3 2 1

• Kod źródłowy Zadanie 1