Sortowanie Pasmami

Wstęp

Algorytm Sortowania Pasmami polega na wyborze takich elementów z listy, które tworzą ciąg monotoniczny. Następnie wybrany ciąg liczb scala się z dotychczas utworzonymi w taki sposób, aby tworzyły ciąg monotoniczny. Jego złożoność jest zależna od ustawienia elementów na liście.

Opis algorytmu

Dla pewnej listy elementów L szukamy od lewej do prawej elementów, które ustawione w kolejności występowania w L tworzą ciąg monotoniczny. Zazwyczaj przyjmuje się pierwszy element za początek ciągu i przegląda kolejne elementy w celu znalezienia elementu warunek posortowania. Wszystkie te elementy tworzą posortowany ciąg T i są usuwane z L. Lista T jest następnie scalane z dotychczas posortowanymi danymi tak, aby zachować monotoniczność. Instrukcje te są powtarzane tak długo, aż lista L będzie pusta.

Przykład

Przyjmijmy, że lista L := {10, 1, 4, 7, 5, 6, 2, 3}. Kolejno zostaną wykonane następujące kroki:

Po posortowaniu listy otrzymano listę W := {1, 2, 3, 4, 5, 6, 7, 10}.

Złożoność

Algorytm bardzo dobrze sobie radzi z listami liczb prawie posortowanymi. Wtedy ilość kroków jest minimalna (nawet jedno dla listy posortowanej) i bliska liniowej O(n). Jednak dla listy liczb posortowanej odwrotnie algorytm wykonuje n + (n - 1) + (n - 2) + .. + 1 porównań co sprawia, że jego złożoność pesymistyczna wynosi O(n²). W kwestii zużycia pamięci to najwięcej danych do przepisania jest dla listy posortowanej i wtedy potrzeba, aż n dodatkowych pozycji na elementy, więc złożoność jest liniowa O(n).

Implementacja

Strategia

Proces wyszukiwania ciągów monotonicznych w rozwiązaniu zostanie ograniczony do wyboru pierwszego elementu z danej listy jako pierwszy ciągu, a następnie cały ciąg zostanie sprawdzony w poszukiwaniu kolejnych jego elementów. W przypadku łączenie wybranych elementów z aktualną listą posortowaną zostanie zastosowany algorytm, który będzie wstawiał nowo wybrane elementy w odpowiednie miejsca do listy wynikowej.

Rozwiązanie

Przedstawiona poniżej funkcja sortuj() przyjmuje jeden argument: lista - lista liczb do posortowania, a wynikiem działania funkcji jest lista posortowanych liczb. Zakłada się, że sortowane są liczby całkowite.

1. vector<int> sortuj(vector<int> lista) {
2.   vector<int> wynik;
3.   while (lista.size() > 0) {
4.     vector<int> bufor;
5.     int ostatni = INT_MIN;
6.     for (int i = 0; i < lista.size(); i++) {
7.       if (lista[i] > ostatni) {
8.         bufor.push_back(lista[i]);
9.         ostatni = lista[i];
10.         lista.erase(lista.begin() + i, lista.begin() + i + 1);
11.         i--;
12.       }
13.     }
14.     int i_bufor = 0, i_wynik = 0;
15.     while (i_wynik < wynik.size() && i_bufor < bufor.size()) {
16.       if (bufor[i_bufor] < wynik[i_wynik]) {
17.         wynik.insert(wynik.begin() + i_wynik, bufor[i_bufor]);
18.         i_bufor++;
19.       }
20.       i_wynik++;
21.     }
22.     while (i_bufor < bufor.size())
23.       wynik.push_back(bufor[i_bufor++]);
24.   }
25.   return wynik;
26. }

(2.) Przygotuj zmienną do zapisu wyniku, a następnie (3.) dopóki nie wybrano wszystkich elementów z listy wejściowej wykonuj następujące instrukcje: przygotuj (4.) miejsce pod wybrane elementy i (5.) nie wybieraj początkowo żadnego elementu. Pierwszy etap (6. - 13.) polega na wybraniu pewnego ciągu liczb. Po (7.) znalezieniu odpowiedniego elementu należy (8.) przepisać go do listy wybranych elementów, (10.) ustawić ostatnio wybrany element i (11.) usunąć element z listy pamiętając, że (12.) następny element na liście ma ten sam indeks co obecnie wybrany element. Drugi etap to (14. - 23.) połączenie nowo wybranych elementów z obecną listą wynikową. Część elementów (14. - 21.) jest wstawiana do listy wynikowej podczas jej przeglądania. Nie wstawione elementy są większe niż wszystkie do tej pory posortowane, więc (22. - 23.) je dopisać na końcu.

Testowanie funkcji

W celu sprawdzenia poprawności działania napisanej funkcji istnieje możliwość skorzystania z poniższego fragmentu kodu, który wczyta dane i wypisze wynik działania funkcji.

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

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję sortuj(), która podczas wybierania kolejnych elementów będzie sprawdzała czy kolejny element można dopisać na początku lub na końcu listy wybranych elementów.

Przykład

Przyjmijmy, że lista L := {10, 1, 4, 7, 5, 6, 2, 3}. Kolejno zostaną wykonane następujące kroki:

Po posortowaniu listy otrzymano listę W := {1, 2, 3, 4, 5, 6, 7, 10}. W tym przypadku lista wynikowa została otrzymana w mniejszej ilości kolejnych wyborów elementów z listy niż w oryginalnym przykładzie, ale należy pamiętać, że w każdej pętli jest wykonywane dwa razy więcej porównań.

• Kod źródłowy Zadanie 1