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. static List<int> sortuj(List<int> lista) {
  2.   List<int> wynik = new List<int>();
  3.   while (lista.Count > 0) {
  4.     List<int> bufor = new List<int>();
  5.     int ostatni = int.MinValue;
  6.     for (int i = 0; i < lista.Count; i++) {
  7.       if (lista[i] > ostatni) {
  8.         bufor.Add(lista[i]);
  9.         ostatni = lista[i];
  10.         lista.RemoveAt(i);
  11.         i--;
  12.       }
  13.     }
  14.     int i_bufor = 0, i_wynik = 0;
  15.     while (i_wynik < wynik.Count && i_bufor < bufor.Count) {
  16.       if (bufor[i_bufor] < wynik[i_wynik]) {
  17.         wynik.Insert(i_wynik, bufor[i_bufor]);
  18.         i_bufor++;
  19.       }
  20.       i_wynik++;
  21.     }
  22.     while (i_bufor < bufor.Count)
  23.       wynik.Add(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. static void Main(string[] args) {
  2.   Console.Write("Ile elementów ma lista?\n n = ");
  3.   int n = Convert.ToInt32(Console.ReadLine());
  4.   List<int> tab = new List<int>();
  5.   Console.WriteLine("Podaj elementy:");
  6.   while (n-- > 0) {
  7.     int t = Convert.ToInt32(Console.ReadLine());
  8.     tab.Add(t);
  9.   }
  10.   List<int> wynik = sortuj(tab);
  11.   Console.WriteLine("Posortowana lista:");
  12.   for (int i = 0; i < wynik.Count; i++)
  13.     Console.Write("{0} ", wynik[i]);
  14.   Console.ReadKey();
  15. }

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