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

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

• 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