Strona główna » Algorytmy » Sortowanie » Sortowanie na Stosach
 

Sortowanie na Stosach

https://mattomatti.com/fs26

Wstęp

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.

Algorytm

Przypuśćmy, że dana jest tablica liczb L. W celu jej posortowania przygotuj dwa stosy: wynikowy oraz tymczasowy. Kolejno wykonuj:

  1. Pobierz kolejny element el z tablicy, jeśli niemożliwe to przejdź do punktu
  2. Przenoś elementy z wynikowego stosu na tymczasowy, aż będzie pusty lub na wierzchu znajdzie się element większy od pobranego elementu el
  3. Wstaw element el na stos wynikowy
  4. Przełóż elementy ze stosu tymczasowego na wynikowy i przejdź do punktu (1.)
  5. Zdejmi wszystkie kolejne elementy ze stosu wynikowego i nadpisuj kolejne elementy w tablicy

Przykład

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:

WstawianyStos WynikowyStos TymczasowyOperacja
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].

Implementacja

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.

Rozwiązanie

Przykładowe rozwiązanie wygląda następująco:

  1. void sortuj(int* tab, int n) {
  2.   stack<int> st_gotowy;
  3.   stack<int> st_tmp;
  4.   for (int i = 0; i < n; i++) {
  5.     while (!st_gotowy.empty() && st_gotowy.top() <= tab[i]) {
  6.       st_tmp.push(st_gotowy.top());
  7.       st_gotowy.pop();
  8.     }
  9.     st_gotowy.push(tab[i]);
  10.     while (!st_tmp.empty()) {
  11.       st_gotowy.push(st_tmp.top());
  12.       st_tmp.pop();
  13.     }
  14.   }
  15.   for (int i = 0; i < n; i++) {
  16.     tab[i] = st_gotowy.top();
  17.     st_gotowy.pop();
  18.   }
  19. }

(2. - 3.) Przygotuj stosy. Następnie (4.) dla każdego elementu tablicy: (5. - 8.) znajdź gdzie należy go aktualnie położyć na stosie, a następnie (9.) wstaw i-ty element i (10. - 13.) przełóż z powrotem elementy ze stosu tymczasowego. Na koniec (15. - 18.) dane ze stosu zostają przepisane na tablice.

Testowanie funkcji

Działanie napisanej funkcji można sprawdzić przy pomocy poniższego fragmentu kodu:

  1. int main() {
  2.   int n;
  3.   cout << "Ile elementow ma lista?\n n = ";
  4.   cin >> n;
  5.   int* tab = new int[n];
  6.   cout << "Podaj elementy:" << endl;
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   sortuj(tab, n);
  10.   cout << "Posortowana lista:" << endl;
  11.   for (int i = 0; i < n; i++)
  12.     cout << tab[i] << " ";
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

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ć.