Wszystko, co chciałeś wiedzieć o algorytmach sortujących, ale o co nie miałeś śmiałości zapytać

https://xpil.eu/yyc

Jak powszechnie wiadomo[citation needed] w świecie komputerów trwa odwieczna walka o wydajność, szybkość, prędkość, błyskawiczność i tak dalej.

Zaczęło się od megaherców, które w parę lat zamieniły się w gigaherce. Po dotarciu do granic częstotliwości zaczął sie wyścig na rdzenie obliczeniowe, koprocesory...

Koprocesor to w skrócie cesor cierpiący na koprofilię.

..., pojawiły się karty graficzne wyspecjalizowane w szybkich równoległych obliczeniach (ilość rdzeni w porządnej karcie graficznej dochodzi dziś do kilku tysięcy!) - wszystko po to, żeby przetworzyć więcej danych w mniejszej ilości czasu.

Tymczasem jednak można też w drugą stronę!

Dziś pokażę, jak pomysłowy jest rodzaj ludzki jeśli chodzi o spowalnianie obliczeń.

Na warsztat weźmiemy proste zadanie polegające na posortowaniu listy elementów w porządku rosnącym.

Na chwilę obecną najszybszym znanym algorytmem sortującym jest QuickSort, chociaż w zależności od różnych czynników może się okazać, że czasem odrobinę szybszy będzie HeapSort lub MergeSort. Wszystkie trzy działają średnio w czasie proporcjonalnym do n log(n), każda z metod ma swoje wady i zalety.

Czy da się inaczej?

Oczywiście!

Można na przykład zastosować sortowanie przez wybieranie: najpierw wyszukujemy w całej tablicy najmniejszy element i zamieniamy go z elementem znajdującym się na pozycji pierwszej. Następnie wśród pozostałych elementów (a więc począwszy od pozycji 2) szukamy znów najmniejszego elementu i zamieniamy go z tym na pozycji 2. Powtarzamy czynność dla kolejnych pozycji, aż dojdziemy do ostatniego elementu na liście.

Tu średni czas sortowania będzie proporcjonalny do kwadratu ilości elementów.

Podobnie szybko będzie działać sortowanie bąbelkowe:

  1. Porównujemy elementy na pozycjach 1 i 2, jeżeli drugi jest mniejszy od pierwszego, zamieniamy je miejscami.
  2. Przesuwamy się na pozycje 2-3, porównujemy drugi element z trzecim, jeżeli są nie po kolei, zamieniamy je miejscami
  3. Przesuwamy się na pozycje 3-4... i tak dalej aż dotrzemy do końca listy.
  4. Jeżeli podczas naszej wędrówki wykonaliśmy chociaż jedną zamianę, zaczynamy od nowa od pozycji 1-2. Jeżeli nie, lista jest posortowana.

Algorytm nazywa się "bąbelkowy", bo duże elementy wędrują pomału w górę listy niczym bąbelki powietrza w wodzie gazowanej.

Czy da się inaczej?

Da się!

SleepSort to algorytm polegający na tym, że dla każdego (numerycznego!) elementu listy czekamy asynchronicznie tyle jednostek czasu, ile wynosi wartość tego elementu, a następnie wypisujemy wartość tego elementu na ekranie. W ten sposób elementy o mniejszych wartościach pojawią sie na ekranie przed elementami większymi. Szczegóły tego algorytmu opisywałem tutaj: http://xpil.eu/IOC4G - czas wykonania zależy tu od wartości największego elementu, a nie od ich ilości, więc w najgorszym razie może się okazać, że na posortowanie dwóch elementów trzeba będzie czekać dłużej, niż wynosi wiek Wszechświata. Aczkolwiek zawsze można znormalizować elementy przed rozpoczęciem sortowania, więc technicznie nie jest to wcale taki najgorszy algorytm.

Da się inaczej?

Da się!

Sortowanie spaghetti (działa tylko dla liczb!) polega na tym, że dla każdej liczby na liście wybieramy jedną nitkę spaghetti (surowego!) o długości odpowiadającej wartości tej liczby. Następnie bierzemy wszystkie te nitki spaghetti w garść (dla długich list możemy potrzebować kogoś z naprawdę wielkimi dłońmi) i opieramy pionowo na jakiejś płaskiej powierzchni. Następnie powoli opuszczamy drugą (płaską) dłoń z góry. Nitka spaghetti, której dotkniemy jako pierwszej, będzie odpowiadać największej liczbie na liście. Wyciągamy tę nitkę i zapisujemy liczbę. Kolejna nitka będzie odpowiadać drugiej największej liczbie - zapisujemy ją obok poprzednio zapisanej największej. Operację powtarzamy aż skończą się nitki spaghetti. Lista będzie posortowana malejąco (chyba, że odwrócimy ją do góry nogami, wtedy rosnąco)

Prędkość działania tego algorytmu zależy od wielu czynników (dokładność pomiaru długości nitki, rodzaj ciasta, płaskość dłoni i tak dalej). W przybliżeniu przyjmuje się, że czas sortowania jest tu proporcjonalny do ilości elementów, ale pamiętajmy, że reprezentacja wiązki spaghetti w komputerze może być o wiele bardziej złożona od zwykłej listy.

Da się inaczej?

Da się!

JingleSort to algorytm działający najlepiej w okresie Świąt Bożego Narodzenia: każdemu elementowi na liście przypisujemy wartość numeryczną, a następnie kupujemy prezenty o wartościach odpowiadających poszczególnym elementom i dajemy je dzieciom. Dzieci, jako istoty z gruntu wredne i złośliwe, natychmiast porównają między sobą wartości prezentów i ustawią się w kolejności dyskryminującej dzieci biedniejsze, a więc po kolei od najtańszego prezentu aż po najdroższy.

Czy da się inaczej?

Da się!

Sortowanie typu BogoSort działa tak:

  1. Losujemy kolejność wszystkich elementów tablicy
  2. Sprawdzamy, czy tablica jest posortowana.
  3. Jeżeli nie jest, wracamy do punktu pierwszego.

Prawdopodobieństwo, że n-elementowa lista będzie posortowana po pierwszym kroku, wynosi 1/(n!). Algorytm działa więc całkiem nieźle dla list krótkich (2-3 elementy), natomiast mocno spowalnia przy listach dłuższych.

Da się inaczej?

Da się!

BozoSort, bardzo podobny wydajnościowo do BogoSort, działa tak:

  1. Sprawdzamy, czy lista jest posortowana, jeżeli tak, koniec.
  2. Wybieramy dwa losowe elementy z listy, zamieniamy je miejscami
  3. Przechodzimy do kroku 1.

Da się inaczej?

Da się!

Roy Therle zaproponował swego czasu ulepszenie algorytmu BozoSort polegające na tym, że oprócz zamiany miejscami dwóch losowych elementów dodatkowo odwracamy kolejność elementów znajdujących się pomiędzy nimi. Dzięki temu co prawda nie zmniejszymy prawdopodobieństwa uzyskania posortowanej listy, ale z pewnością zwiększymy zużycie pamięci i procesora.

Da się inaczej?

Da się!

Bliskim krewnym algorytmu BogoSort jest algorytm BogoBogoSort, który działa tak:

  1. Bierzemy pierwszy element z listy.
  2. Sortujemy go algorytmem BogoSort (będzie posortowany przy pierwszym podejściu, bo jest tylko jeden)
  3. Bierzemy drugi element z listy, dołączamy go na koniec naszej posortowanej listy z punktu 2.
  4. Sortujemy naszą listę dwóch elementów algorytmem BogoSort.
  5. Powtarzamy czynność dla elementu trzeciego: dołączamy go na koniec listy, sortujemy listę BogoSort-em.
  6. Kontynuujemy aż do wyczerpania wszystkich elementów.

Przy dłuższych listach algorytm BogoBogoSort w zasadzie gwarantuje, że śmierć cieplna Wszechświata nastąpi przed posortowaniem naszej listy.

Na zakończenie kilka algorytmów, których poprawność jeszcze nie została udowodniona, ale które z dużym prawdopodobieństwem działają poprawnie:

Sortowanie Cudowne:

1. Sprawdź czy lista jest posortowana.
2. Jeżeli nie, poczekaj chwilę i przejdź do punktu pierwszego.

Wyjaśnienie: w rzadkich przypadkach losowe promieniowanie Alfa potrafi zmienić zawartość pojedynczego bitu w pamięci RAM. Istnieje więc szansa, że po upływie odpowiednio długiego czasu takie losowe zmiany doprowadzą do posortowania listy.

Sortowanie Kwantowe:

1. Sprawdź, czy lista jest posortowana. Jeżeli nie, zniszcz wszechświat.

Wyjaśnienie: jeżeli - zgodnie z tym, co przewiduje mechanika kwantowa - istnieje tyle światów równoległych, co możliwych stanów kwantowych, wówczas po zakończeniu tego algorytmu wszystkie światy, w których lista jest nieposortowana, zostaną zniszczone i pozostaną wyłącznie te, w których lista jest posortowana. Niestety, ponieważ wraz ze zniszczeniem wszechświata znika również jego czas, trudno jest określić złożoność czasową tego algorytmu. Niewykluczone, że czas wykonania wynosi zero.

Sortowanie Pi:

  1. Wyznaczamy ilość cyfr w indeksie ostatniego elementu listy (np. jeżeli lista jest 1000-elementowa, indeksowana od 0, ostatni element ma indeks 999, czyli trzy cyfry)
  2. Dzielimy rozwinięcie dziesiętne liczby Pi na segmenty o rozmiarze ustalonym w poprzednim kroku.
  3. Zamieniamy miejscami element na pozycji określonej przez pierwszy segment z elementem na pozycji określonej przez drugi segment. Potem trzeci z czwartym piąty z szóstym i tak dalej. Jeżeli natkniemy się na numer segmentu wykraczający poza ostatni element listy, przesuwamy całość o jedno miejsce dziesiętne w górę i zaczynamy od nowa.
  4. Po każdej zamianie sprawdzamy, czy lista jest posortowana.

Jako ostatni zaprezentuję algorytm - perełkę, zdecydowanie najciekawszy z tu wymienionych.

Algorytm Inteligentnego Projektu:

Wstęp:

Algorytm Inteligentnego Projektu oparty jest na teorii inteligentnego projektu.

Opis:

Prawdopodobieństwo, że lista będzie od razu posortowana wynosi 1/(n!). Szansa, że tak będzie, jest tak nikła, że byłoby kompletną bzdurą twierdzić, że wydarzyło się to przypadkiem. Ktoś musiał świadomie poustawiać elementy listy w takiej a nie innej kolejności. Tym kimś jest Wszechmocny Sortownik. Dlatego można spokojnie przyjąć, że lista jest już posortowana optymalnie według zasad, które wykraczają poza naiwne wyobrażenia śmiertelników o sortowaniu. Jakakolwiek próba zmiany kolejności elementów na liście sprawi, że będzie ona mniej posortowana.

Analiza:

Algorytm jest stały w czasie i sortuje listę natychmiastowo, nie wymagając żadnej pamięci operacyjnej ani żadnych innych podejrzanych urządzeń elektrycznych czy elektronicznych. Chwalmy Sortownika!

https://xpil.eu/yyc

6 komentarzy

  1. @Sortowanie Kwantowe- raczej lepiej będzie zmieniać wszechświat na kolejny [ale taki, którego w ramach tego algorytmu nie odwiedzaliśmy]. Inna sprawa, że wtedy zakładamy istnienie meta wszechświata, który zawiera w sobie inne wszechświaty [z różnymi wariatami list].

    Imho prościej [i chyba bardziej [human|alien]itarnie] będzie “po prostu” stworzyć w jednym wszechświecie wszystkie wariancje listy i wybrać posortowaną…

    1. Stworzenie wszystkich wariantów? Ale one już są przecież, tylko w innych wszechświatach. {Huma|Alie}nitarność nie ma tu nic do rzeczy, niszczenie wszechświatów z nieposortowanymi wersjami listy odbywa się momentalnie, nikt nie cierpi.

      1. co do natychmiastowości to bym dyskutował..
        Pomijając ograniczenie co do prędkości światła – zobacz co się dzieje po skasowaniu pliku – zmieniany jest tylko znacznik. A tam może dalej grać orkiestra – jak na Titanicu.
        Albo może istnieć inna aktywność – do czasu aż garbage collector zrobi swoje..

        Wszystko jest kwestią implementacji.

        1. Prędkość światła to ograniczenie narzucone naszemu wszechświatowi, ale z uprawnieniami roota jest do obejścia…

          Co do garbage collectora zaś, aż dziwne że jeszcze nie zajął się moim blogiem.

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.