Strona główna » Algorytmy » Sortowanie » Sortowanie Przez Spanie
 

Sortowanie Przez Spanie

https://mattomatti.com/fs21

Cel

Sortowanie Przez Spanie jest algorytmem sortowania, który zawsze działa tylko w rzeczywistym świecie. Jako program nie zawsze musi zwrócić prawidłowych wyników, ale jest to spowodowane sposobem wykonywania programów przez komputer.

Opis Działania

Każda liczba dodatnia, całkowita umieszczona na liście oznacza jak długo powinien dany element spać. Zakładając, że wszystkie elementy pójdą spać równocześnie to będą one wstawać w kolejności posortowanej.

Przykład

Przykładowo niech do posortowania będzie lista liczb L:={5, 1, 3, 2, 4}. W poniższej tabelce każdy kolejny wiersz oznacza i-tą jednostkę czasu, a w każdej kolumnie zostało opisane ile snu zostało danemu elementowi. W każdej jednostce czasu obudzony element zgłasza się do wpisania na tablice.

Czas51324Lista wynikowa
051324{}
14!213{1}
23 1!2{1, 2}
32 ! 1{1, 2, 3}
41   !{1, 2, 3, 4}
5!    {1, 2, 3, 4, 5}

Tablica została posortowana, otrzymano L':={1, 2, 3, 4, 5}

Złożoność i Uwagi

Algorytm Sortowania Przez Spanie ma złożoność pamięciową O(n), ponieważ istnieje potrzeba utworzenia n dodatkowych wątków. Z kolei złożoność czasowa jest O(p·t), gdzie p - to element o największej wartości na liście, a t - to czas wykonania się jednej jednostki czasu. Innymi słowy złożoność czasowa algorytmu zależy przede wszystkim od tego jak duże dane są do posortowania.

Jednym z problemów związanych z wykonaniem tego algorytmu jest potrzeba precyzji obsłużenia obudzonego procesu. Obecne komputery nie gwarantują, że dany wątek obudzi się dokładnie za n jednostek czasu, ponieważ są różne metody wyboru następnego wątku do wykonania. Oznacza to, że jest szansa, że zostaną obsłużone w złej kolejności. Rozwiązaniem tego problemu jest zwiększenie ilości jednostek czasu pomiędzy czasami snu elementów. Należy jednak pamiętać, że im większy ten czas tym dłużej będzie się wykonywał. Przykładowo algorytm, gdzie t = 100ms, a p = 10 wyniesie już 1s! W tym czasie algorytm QuickSort jest w stanie posortować blisko 107 elementów!

Implementacja

Usypianie elementów jest możliwe poprzez tworzenie nowych, dodatkowych wątków programu. Kiedy wątek obudzi się zgłosi głównemu programowi, że ma zapisać jego tablicę na listę. Funkcja sortująca będzie przyjmować listę do posortowania oraz czas t, który określi różnicę czasu pomiędzy pobudkami dwóch kolejnych elementów pod względem wartości.

C++
C#
  1. struct Dane {
  2.   public int[] dane;
  3.   public int i, t, pos;
  5.   public Dane(int[] dane, int i, ref int t, ref int pos) {
  6.     this.dane = dane;
  7.     this.i = i;
  8.     this.t = t;
  9.     this.pos = pos;
  10.   }
  11. }
  13. static void Uśpij(object element) {
  14.   Dane d = (Dane)element;
  15.   Thread.Sleep(1000 * d.t * d.dane[d.i]);
  16.   d.dane[d.pos++] = d.dane[d.i];
  17. }
  19. static void sortuj(int[] dane, int t) {
  20.   int pos = 0;
  21.   for (int i = 0; i < dane.Length; ++i) {
  22.     Thread thread = new Thread(Uśpij);
  23.     thread.Start(new Dane(dane, i, ref t, ref pos));
  24.   }
  25. }

(1. - 11.) Struktura Dane pozwala na przesłanie informacji do tworzonego wątku. Zawiera nastęujące informacje: dane - tablica do zapisu danych, i - numer elementu usypianego, t - różnica czasu pomiędzy pobudkami (w sekundach) oraz pos - pozycja zapisu w tablicy wyniku (wspólne dla wszystkich wątków). (13. - 17.) Uśpienie procesu polega na (14.) pobraniu danych, (15.) uśpienia wątku i (16.) zapisu wyniku w tablicy po obudzeniu. Elementy usypia (19. - 25.) funkcja sortuj().

Testowanie funkcji

Poniższy kod pozwala przetestować funkcję sortuj(). Po uruchomieniu program wczyta od użytkownika potrzebne dane, a następnie posortuje tablice i ją wypisze.

C++
C#
  1. static void Main(string[] args) {
  2.   Console.Write("Podaj ile jest elementow\n n = ");
  3.   int n = Convert.ToInt32(Console.ReadLine());
  4.   int[] tab = new int[n];
  5.   Console.WriteLine("Podaj elementy:");
  6.   for (int i = 0; i < n; i++)
  7.     tab[i] = Convert.ToInt32(Console.ReadLine());
  8.   Console.Write("Różnica czasu pomiędzy pobudkami\n t = ");
  9.   int t = Convert.ToInt32(Console.ReadLine());
  10.   sortuj(tab, t);
  11.   Console.WriteLine("Po posortowaniu:");
  12.   for (int i = 0; i < n; i++)
  13.     Console.Write("{0} ", tab[i]);
  14.   Console.ReadKey();
  15. }