Strona główna » Algorytmy » Sortowanie » Sortowanie Pasmami
 

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:

Lista LWybrane
elementy
Lista
Posortowana
{1, 10, 4, 7, 5, 6, 2, 3}{1, 10}{ }
{4, 7, 5, 6, 2, 3}{4, 7}{1, 10}
{5, 6, 2, 3}{5, 6}{1, 4, 7, 10}
{2, 3}{2, 3}{1, 4, 5, 6, 7, 10}
{ }-{1, 2, 3, 4, 5, 6, 7, 10}

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(n2). 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.

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

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

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:

Lista LWybrane
elementy
Lista
Posortowana
{1, 10, 4, 7, 5, 6, 2, 3}{1, 10}{ }
{4, 7, 5, 6, 2, 3}{2, 4, 7}{1, 10}
{5, 6, 3}{3, 5, 6}{1, 2, 4, 7, 10}
{ }-{1, 2, 3, 4, 5, 6, 7, 10}

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