Sortowanie Przez Spanie

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.

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

1. void sortuj(unsigned int* dane, int n, int t) {
2.   std::vector<std::thread> threads;
3.   int pos = 0;
4.   for (int i = 0; i < n; ++i) {
5.     threads.emplace_back([dane, i, t, &pos]() {
6.       int w = dane[i];
7.       this_thread::sleep_for(chrono::seconds(w*t));
8.       dane[pos++] = w;
9.     });
10.   }
11.   for (auto& thread : threads)
12.     thread.join();
13. }

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.

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.

1. int main() {
2.   unsigned int n, t;
3.   cout << "Podaj ile jest elementow\n n = ";
4.   cin >> n;
5.   unsigned int* tab = new unsigned int[n];
6.   cout << "Podaj elementy:\n";
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   cout << "Roznica czasu pomiedzy pobudkami (s)\n t = ";
10.   cin >> t;
11.   sortuj(tab, n, t);
12.   cout << "Po posortowaniu:\n";
13.   for (int i = 0; i < n; i++)
14.     cout << tab[i] << " ";
15.   system("pause");
16.   return 0;
17. }

• Kod źródłowy Implementacja