Lepsze sorty i gorsze sorty

Data publikacji: 2015-12-22 | Tagi:

Nie sposób uciec przed polityką. No i doszło do tego, że i na moim blogu znajdzie się post wpisujący się w obecną kulturę języka politycznego. Konkretnie napiszę dziś o najgorszych sortach.

Postaram się zacząć od tych najlepszych złych sortów i powoli przesuwał się będę w stronę sortów najgorszych z najgorszych.

BogoSort

Pseudokod algorytmu:

    while not is_in_order(deck):
        shuffle(deck)

W skrócie - sprawdź, czy lista jest posortowana, jeśli nie, zrandomizuj ją i wróć do początku.

Istnieje kilka algorytmów pochodnych, np. Gorosort, Bogobogosort itp. ich wspólną cechą jest to, że polegają na randomizowaniu części lub całości listy i że w ekstremalnych warunkach mogą posortować listę w jednej iteracji.

BogoSort jest jednym z mniej zakręconych algorytmów opisanych w tym artykule, ponieważ tuż za nim nadchodzi...

ImpossibleSort

Pseudokod algorytmu:

    come_on_sort_it_dude(deck)

Po prostu weź to i posortuj. Ten algorytm powstał wcześniej niż maszyny liczące. Niestety do tej pory nie powstał dokłaniejszy opis. Stąd też jego nazwa odnosząca się nie do działania, ale do jego opisu.

Może być wysoce wydajny, jeśli chodzi o sortowanie przypraw alfabetycznie w przyprawniku, ale może okazać się zupełnie niewydajny, jeśli chodzi o sortowanie książek na półce względem wielkości.

IntelligentDesignSort

Pseudokodu algorytmu brak. Jest tylko słowny opis, a brzmi on mniej więcej tak:

Prawdopodobieństwo umieszczenia danej n-elementowej listy w konkretnym porządku jest równe 1/(n!). Jest to prawdopodobieństwo tak małe, że byłoby absurdalnym myśleć, iż stało się to przez przypadek. Zatem musiały być umieszczone w tym konkretnym porządku przez inteligentnego Sortera. Zatem można bezpiecznie założyć, że elementy tak ułożone zostały umieszczone na swoich miejscach optymalnie posortowane i głęboko przekraczające nasze ludzkie postrzeganie pojęcia "rosnąco" bądź "malejąco". Każda próba wpłynięcia na zadaną kolejność, aby pasowała do ludzkich pojęć sprawi, że realnie dana lista stanie się mniej posortowana.

Algorytm jest teoretycznie stały w czasie, ale implikuje użycie czasu do sortowania, co byłoby obrazą dla Inteligentnego Sortera. Chwalmy Go!

MiracleSort

Pseudokod algorytmu:

    while not is_in_order(deck):
         wait()

Sprawdzamy, czy lista jest posortowana, jeśli nie, to czekamy określoną ilość czasu i sprawdzamy ponownie, mając nadzieję, że lista cudownym sposobem posortuje się sama.

QuantumBogoSort

Wariacja algorytmu BogoSort. Oto pseudokod:

    while not is_in_order(deck):
        destroy_universe()
        move_to_another_universe()

Jeśli w danym wszechświecie lista nie jest posortowana, niszczymy bieżący wszechświat i przenosimy się do następnego, sprawdzając ponownie.

StepBackSort

Pseudokod algorytmu:

    while you_can_see_order(deck) and not is_in_order(deck):
        take_step_back()

Sprawdzamy, czy jesteśmy w stanie zobaczyć kolejność listy i czy w związku z tym lista jest posortowana. Jeśli nie to robimy krok do tyłu. Jeśli nie damy rady dostrzec listy to nie jesteśmy w stanie określić jej stanu posortowania, a zatem całą sprawę możemy uznać za niebyłą.

Ten algorytm wymaga udziału czynnika białkowego.

ReplacementSort

Pseudokod algorytmu:

    while not is_in_order(deck):
        deck = []

Jeśli lista nie jest posortowana, to zastępujemy ją pustą listą, która jest posortowana z natury.

Ten algorytm charakteryzuje się wysoką szybkością działania - zadowalające wyniki możemy mieć w pierwszej iteracji.

To były chyba wszystkie najgorsze sorty jakie znam.

Przy pisaniu postu korzystałem z wikipedii, stackoverflow, google i swojej nieposortowanej głowy.


Oceń ten post:
Podziel się:

comments powered by Disqus

IT w obrazkach: