Sortowanie na Stosach wykorzystuje do sortowania kolejke LIFO. Algorytm ten przypomina Sortowanie przez Wstawianie, ponieważ każdy kolejny element jest układany na stosie w odpowiednie miejsce.
Przypuśćmy, że dana jest tablica liczb L. W celu jej posortowania przygotuj dwa stosy: wynikowy oraz tymczasowy. Kolejno wykonuj:
Niech tablica danych posortowania to będzie L:=[4, 1, 2, 5, 3]. Początkowo stosy są puste. Kolejne operacje zostały przedstawione w tabeli:
| Wstawiany | Stos Wynikowy | Stos Tymczasowy | Operacja |
|---|---|---|---|
| 4 | {} | {} | stos wynikowy pusty, kładziemy 4 |
| 1 | {4} | {} | 1 < 4, więc kładziemy |
| 2 | {4, 1} | {} | 2 > 1, więc przekładamy 1 na stos tymczasowy |
| 2 | {4} | {1} | 2 < 4, więc kładziemy wstawianą wartość |
| {4, 2} | {1} | przekładamy z stosu tymczsowego na wynikowy | |
| 5 | {4, 2, 1} | {} | 5 > 1, więc przekładamy 1 |
| 5 | {4, 2} | {1} | 5 > 2, więc przekładamy 2 |
| 5 | {4} | {1, 2} | 5 > 4, więc przekładamy 4 |
| 5 | {} | {1, 2, 4} | stos wynikowy pusty, kładziemy 5 |
| {5} | {1, 2, 4} | przekładamy z stosu tymczsowego na wynikowy | |
| 3 | {5, 4, 2, 1} | {} | 3 > 1, więc przekładamy 1 |
| 3 | {5, 4, 2} | {1} | 3 > 2, więc przekładamy 2 |
| 3 | {5, 4} | {1, 2} | 3 < 4, więc kładziemy |
| {5, 4, 3} | {1, 2} | przekładamy z stosu tymczsowego na wynikowy | |
| - | {5, 4, 3, 2, 1} | {} | - |
Na koniec należy zdejmować kolejne elementy ze stosu i zastępować kolejne elementy z tablicy. Posortowana tablica L to [1, 2, 3, 4, 5].
Zadanie polega na napisaniu algorytmu do sortowania danych przy pomocy dwóch stosów opisanego wyżej. Program powinien wczytać tablice od użytkownika (jej rozmiar i dane), a następnie wypisać posortowane dane.
Przykładowe rozwiązanie wygląda następująco:
(2. - 3.) Przygotuj stosy. Następnie (4.) dla każdego elementu tablicy: (5. - 7.) znajdź gdzie należy go aktualnie położyć na stosie, a następnie (8.) wstaw i-ty element i (9. - 11.) przełóż z powrotem elementy ze stosu tymczasowego. Na koniec (12. - 14.) dane ze stosu zostają przepisane na tablice.
Działanie napisanej funkcji można sprawdzić przy pomocy poniższego fragmentu kodu:
Napisz funkcję, która wykona jak najmniejszą ilość przełożeń pomiędzy stosami. Jest możliwe, aby ze stosu tymczasowego przekładać mniej danych. Można to zrobić znając następną wstawianą liczbę i przełożyć tylko tyle, aby od razu można było kolejną liczbę położyć.