Czy są jakieś gorsze algorytmy sortowania niż Bogosort (inaczej Monkey Sort)? [Zamknięte]

Moi współpracownicy zabrali mnie w czasie do moich dni na uniwersytecie, omawiając dziś rano algorytmy sortowania. Wspominaliśmy nasze ulubione, takie jak StupidSort , i jeden z nas był pewien, że widzieliśmy algorytm sortowania O(n!). To sprawiło, że zacząłem rozglądać się za „najgorszymi” algorytmami sortowania, jakie udało mi się znaleźć.

Postulowaliśmy, że całkowicie losowe sortowanie byłoby całkiem złe (tj. Losowanie elementów - czy jest w porządku? Nie? Losowanie ponownie), a ja rozejrzałem się i odkryłem, że najwyraźniej nazywa się to BogoSort lub Monkey Sort, a czasem po prostu losowe sortowanie .

Wydaje się, że Monkey Sort ma najgorszy przypadek O(∞), najlepszy przypadek O(n)i średnią wydajność O(n·n!).

Jaki jest obecnie oficjalnie akceptowany algorytm sortowania z najgorszą średnią wydajnością sortowania (a zatem gorszą niż O(n·n!))?

Ze strony Esoteric Algorithms Davida Morgana-Mara : Inteligentne sortowanie projektów

Wprowadzenie

Inteligentne sortowanie projektów to algorytm sortowania oparty na teorii inteligentnego projektu.

Opis algorytmu

Prawdopodobieństwo, że oryginalna lista wejściowa będzie dokładnie w takiej kolejności, w jakiej się znajduje, wynosi 1 / (n!). Jest tak małe prawdopodobieństwo, że stwierdzenie, że stało się to przez przypadek, jest oczywistym absurdem, więc musiało to zostać świadomie uporządkowane przez inteligentnego Sortera. Dlatego można bezpiecznie założyć, że jest już optymalnie Posortowany w jakiś sposób, który przekracza nasze naiwne, śmiertelne rozumienie „porządku wstępującego”. Każda próba zmiany tego porządku, aby dostosować się do naszych własnych uprzedzeń, sprawiłaby, że byłby mniej uporządkowany.

Analiza

Algorytm ten jest stały w czasie i sortuje listę w miejscu, nie wymagając w ogóle dodatkowej pamięci. W rzeczywistości nie wymaga nawet żadnych podejrzanych technologicznych rzeczy komputerowych. Chwała Sorterowi!

Sprzężenie zwrotne

Gary Rogers pisze:

Utrwalenie sortowania w czasie zaprzecza mocy Sortera. Sorter istnieje poza czasem, dlatego jest ponadczasowy. Potrzeba czasu, by zatwierdzić rodzaj, osłabia rolę Sortownika. Zatem ... ten szczególny rodzaj jest wadliwy i nie można go przypisać „The Sorter”.

Herezja!

Wiele lat temu wynalazłem (ale nigdy nie wdrożyłem) MiracleSort.

Start with an array in memory.
loop:
    Check to see whether it's sorted.
    Yes? We're done.
    No? Wait a while and check again.
end loop

Ostatecznie cząstki alfa przerzucające bity w układach pamięci powinny skutkować pomyślnym sortowaniem.

Aby uzyskać większą niezawodność, skopiuj macierz do chronionej lokalizacji i porównaj potencjalnie posortowane tablice z oryginałem.

Jak więc porównać potencjalnie posortowaną tablicę z oryginałem? Po prostu sortujesz każdą tablicę i sprawdzasz, czy pasuje. MiracleSort jest oczywistym algorytmem do użycia w tym kroku.

EDYCJA: Ściśle mówiąc, to nie jest algorytm, ponieważ nie ma gwarancji zakończenia. Czy „nie algorytm” kwalifikuje się jako „gorszy algorytm”?

Quantum Bogosort

Algorytm sortowania, który zakłada, że ​​wieloświatowa interpretacja mechaniki kwantowej jest poprawna:

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

Na zakończenie algorytmu lista zostanie posortowana w jedynym pozostałym wszechświecie. Algorytm ten wymaga czasu dla najgorszego przypadku O (N) i średniego przypadku O (1). W rzeczywistości średnia liczba wykonanych porównań wynosi 2: istnieje 50% szans, że wszechświat zostanie zniszczony na drugim elemencie, 25% szans, że zostanie zniszczony na trzecim i tak dalej.

Dziwię się, że nikt jeszcze nie wspomniał o sleepsort ... Czy nie zauważyłem tego? Tak czy siak:

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

przykład użycia:

./sleepsort.sh 5 3 6 3 6 3 1 4 7
./sleepsort.sh 8864569 7

Pod względem wydajności jest to okropne (zwłaszcza drugi przykład). Czekanie prawie 3,5 miesiąca na sortowanie 2 liczb jest trochę złe.

Jingle Sort, jak opisano tutaj .

W Boże Narodzenie każdą wartość z listy podajesz innemu dziecku. Dzieci, będąc okropnymi istotami ludzkimi, porównają wartość swoich darów i odpowiednio się uporządkują.

Miałem wykładowcę, który kiedyś zasugerował wygenerowanie losowej tablicy, sprawdzenie, czy została posortowana, a następnie sprawdzenie, czy dane są takie same jak tablica do posortowania.

Najlepszy przypadek O (N) (pierwszy raz dziecko!) Najgorszy przypadek O (nigdy)

Jeśli w jakikolwiek sposób utrzymasz znaczenie algorytmu, O(n!)jest to najgorsza górna granica, jaką możesz osiągnąć.

Ponieważ sprawdzenie każdej możliwości posortowania permutacji zestawu będzie wymagało pewnych n!kroków, nie możesz być gorszy.

Jeśli wykonujesz więcej kroków niż to, algorytm nie ma żadnego użytecznego celu. Nie wspominając o następującym prostym algorytmie sortowania z O(infinity):

list = someList
while (list not sorted):
    doNothing

Bogobogosort. Tak, to jest rzecz. do Bogobogosort, Ty Bogosort pierwszy element. Sprawdź, czy ten jeden element jest posortowany. Będąc jednym elementem, będzie. Następnie dodajesz drugi element i Bogosortuj te dwa, aż zostaną posortowane. Następnie dodajesz jeszcze jeden element, a następnie Bogosort. Kontynuuj dodawanie elementów i Bogosortowanie, aż w końcu wykonasz każdy element. Miało to nigdy nie udać się z żadną pokaźną listą przed śmiercią wszechświata.

Powinieneś zbadać ekscytującą dziedzinę algorytmów pesymalnych i analizy prostoty . Autorzy ci zajmują się problemem opracowania sortowania z pesymalnym najlepszym przypadkiem (najlepszym przypadkiem twojego bogosortu jest Omega (n), podczas gdy spowolnienie sortowania (patrz artykuł) ma nie wielomianową złożoność najlepszego przypadku).

Istnieje rodzaj, który nazywa się bogobogosort. Najpierw sprawdza pierwsze 2 elementy i bogosortuje je. Następnie sprawdza pierwsze 3, bogosortuje i tak dalej.

Gdyby lista była w jakimkolwiek momencie nieuporządkowana, jest ona uruchamiana ponownie przez ponowne bogosortowanie pierwszych 2. Zwykły bogosort ma średnią złożoność wynoszącą O(N!), ten algorytm ma średnią złożoność wynoszącąO(N!1!2!3!...N!)

Edycja : Aby dać ci wyobrażenie o tym, jak duża jest ta liczba, w przypadku 20pierwiastków ten algorytm zajmuje średnio 3.930093*10^158 lata , znacznie powyżej proponowanej śmierci cieplnej wszechświata (jeśli tak się stanie) 10^100 lat ,

podczas gdy sortowanie przez scalanie zajmuje około .0000004 sekund , sortowanie bąbelkowe .0000016 sekund , a bogosort zajmuje 308 lata , 139 dni , 19 godziny , 35 minuty , 22.306 sekundy , zakładając, że rok to 365,242 dni, a komputer wykonuje 250 000 000 32-bitowych operacji na liczbach całkowitych na sekundę.

Edit2 : Ten algorytm nie jest tak powolny jak cudowne sortowanie "algorytmem", które prawdopodobnie, podobnie jak ten rodzaj, spowoduje, że komputer zostanie wessany do czarnej dziury, zanim pomyślnie sortuje 20 elementów, ale gdyby tak było, oszacowałbym średnią złożoność od 2^(32(the number of bits in a 32 bit integer)*N)(the number of elements)*(a number <=10^40) lat ,

ponieważ grawitacja przyspiesza ruchy alfa chipów, a istnieją stany 2 ^ N 2^640*10^40, czyli około 5.783*10^216.762162762 lat , chociaż gdyby lista zaczęła się posortowana, jej złożoność byłaby tylko O(N)szybsza niż sortowanie przez scalanie, które wynosi tylko N log N nawet w najgorszym przypadku.

Edit3 : Ten algorytm jest w rzeczywistości wolniejszy niż sortowanie cudowne, ponieważ rozmiar staje się bardzo duży, powiedzmy 1000, ponieważ mój algorytm miałby czas działania 2.83*10^1175546 lat , podczas gdy algorytm cudownego sortowania miałby czas działania 1.156*10^9657 lat .

Oto dwa rodzaje, które wymyśliłem z moim współlokatorem na studiach

1) Sprawdź kolejność 2) Może zdarzył się cud, przejdź do 1

i

1) sprawdź, czy jest w porządku, jeśli nie 2) umieść każdy element w pakiecie i odbij go od odległego serwera z powrotem do siebie. Niektóre z tych pakietów powrócą w innej kolejności, więc przejdź do 1

Zawsze jest Bogobogosort (Bogoception!). Wykonuje Bogosort na coraz większych podzbiorach listy, a następnie rozpoczyna wszystko od nowa, jeśli lista nie zostanie posortowana.

for (int n=1; n<sizeof(list); ++n) {
  while (!isInOrder(list, 0, n)) {
    shuffle(list, 0, n);
  }
  if (!isInOrder(list, 0, n+1)) { n=0; }
}

1 Umieść przedmioty do sortowania na kartach katalogowych.
2 Wyrzuć je w powietrze w wietrzny dzień, milę od domu.
2 Wrzuć je do ogniska i potwierdź, że są całkowicie zniszczone.
3 Sprawdź, czy podłoga w kuchni jest poprawna.
4 Powtórz, jeśli nie jest to właściwa kolejność.

Najlepszym scenariuszem jest O (∞)

Edytuj powyżej na podstawie wnikliwej obserwacji Kenny'egoTM.

Pytanie „co chciałbyś, żeby to było?” sortować

1. Zanotuj czas systemowy.
2. Sortuj używając Quicksort (lub czegokolwiek innego rozsądnego), pomijając ostatnią zamianę.
3. Zanotuj czas systemowy.
4. Oblicz wymagany czas. Arytmetyka o rozszerzonej precyzji jest wymagana.
5. Poczekaj wymagany czas.
6. Wykonaj ostatnią zamianę.

Nie tylko może zaimplementować dowolną wyobrażalną wartość O (x) krótszą od nieskończoności, ale również czas potrzebny jest na udowodnioną poprawność (jeśli możesz czekać tak długo).

Nie ma nic gorszego niż nieskończoność.

Sortowanie Bozo to powiązany algorytm, który sprawdza, czy lista jest posortowana, a jeśli nie, zamienia losowo dwa elementy. Ma te same najlepsze i najgorsze wyniki, ale intuicyjnie spodziewałbym się, że średni przypadek będzie dłuższy niż Bogosort. Trudno jest znaleźć (lub wyprodukować) jakiekolwiek dane na temat wydajności tego algorytmu.

Segmenty π

Załóżmy, że π zawiera wszystkie możliwe kombinacje liczb skończonych. Zobacz pytanie dotyczące math.stackexchange

1. Określ liczbę potrzebnych cyfr na podstawie rozmiaru tablicy.
2. Użyj segmentów miejsc π jako indeksów, aby określić, jak zmienić kolejność tablicy. Jeśli segment przekracza granice rozmiaru dla tej tablicy, dostosuj przesunięcie dziesiętne π i zacznij od nowa.
3. Sprawdź, czy ponownie uporządkowana tablica jest posortowana. Jeśli jest woot, w przeciwnym razie dostosuj przesunięcie i zacznij od nowa.

W najgorszym przypadku wydajność O (∞) może według niektórych nawet nie uczynić go algorytmem .

Algorytm to tylko seria kroków i zawsze możesz zrobić gorzej, poprawiając go trochę, aby uzyskać pożądany wynik w większej liczbie kroków niż poprzednio. Można było celowo umieścić w algorytmie wiedzę o liczbie kroków i sprawić, że będzie się on kończył i dawał poprawny wynik dopiero po wykonaniu określonej Xliczby kroków. XMoże to być równie dobrze rzędu O (n ² ) lub O (n ^n! ), Albo cokolwiek algorytm chciałby zrobić. To skutecznie zwiększyłoby zarówno optymalne, jak i średnie granice przypadków.

Ale najgorszego scenariusza nie da się przebić :)

Moim ulubionym powolnym algorytmem sortowania jest sortowanie z marionetkami:

void stooges(long *begin, long *end) {
   if( (end-begin) <= 1 ) return;
   if( begin[0] < end[-1] ) swap(begin, end-1);
   if( (end-begin) > 1 ) {
      int one_third = (end-begin)/3;
      stooges(begin, end-one_third);
      stooges(begin+one_third, end);
      stooges(begin, end-one_third);
   }
}

Najgorszy przypadek to złożoność O(n^(log(3) / log(1.5))) = O(n^2.7095...).

Inny powolny algorytm sortowania to tak naprawdę powolny!

void slow(long *start, long *end) {
   if( (end-start) <= 1 ) return;
   long *middle = start + (end-start)/2;
   slow(start, middle);
   slow(middle, end);
   if( middle[-1] > end[-1] ) swap(middle-1, end-1);
   slow(start, end-1);
}

Ten trwa O(n ^ (log n))w najlepszym przypadku ... nawet wolniej niż marionetka.

Recursive Bogosort (probably still O(n!){
if (list not sorted)
list1 = first half of list.
list 2 = second half of list.
Recursive bogosort (list1);
Recursive bogosort (list2);
list = list1 + list2
while(list not sorted)
    shuffle(list);
}

Ta strona jest interesującą lekturą na ten temat: http://home.tiac.net/~cri_d/cri/2001/badsort.html

Moim ulubionym jest sillysort Toma Duffa:

/*
 * The time complexity of this thing is O(n^(a log n))
 * for some constant a. This is a multiply and surrender
 * algorithm: one that continues multiplying subproblems
 * as long as possible until their solution can no longer
 * be postponed.
 */
void sillysort(int a[], int i, int j){
        int t, m;
        for(;i!=j;--j){
                m=(i+j)/2;
                sillysort(a, i, m);
                sillysort(a, m+1, j);
                if(a[m]>a[j]){ t=a[m]; a[m]=a[j]; a[j]=t; }
        }
}

Podwójny bogosort

Bogosort dwa razy i porównaj wyniki (aby mieć pewność, że są posortowane), jeśli nie zrób to ponownie

Możesz spowolnić dowolny algorytm sortowania, uruchamiając losowo krok „czy to posortowane”. Coś jak:

1. Utwórz tablicę wartości logicznych o tym samym rozmiarze co sortowana tablica. Ustaw je wszystkie na fałsz.
2. Uruchom iterację bogosort
3. Wybierz dwa losowe elementy.
4. Jeśli dwa elementy są posortowane względem siebie (i <j && tablica [i] <tablica [j]), oznacz indeksy obu w tablicy logicznej na wartość true. Overwise, zacznij od nowa.
5. Sprawdź, czy wszystkie wartości logiczne w tablicy są prawdziwe. Jeśli nie, wróć do 3.
6. Gotowe.

Tak, SimpleSort, teoretycznie działa, O(-1)ale jest to równoważne temu,O(...9999) co z kolei jest równoważne O (∞ - 1), co jak to się dzieje, jest również równoważne O (∞). Oto moja przykładowa realizacja:

/* element sizes are uneeded, they are assumed */
void
simplesort (const void* begin, const void* end)
{
  for (;;);
}

Jeden, nad którym właśnie pracowałem, polega na wybraniu dwóch losowych punktów, a jeśli są w złej kolejności, odwróceniu całego podzakresu między nimi. Algorytm znalazłem na http://richardhartersworld.com/cri_d/cri/2001/badsort.html , który mówi, że przeciętny przypadek jest prawdopodobnie gdzieś w okolicach O (n ^ 3) lub O (n ^ 2 log n) ( nie jest do końca pewien).

Myślę, że można by to zrobić bardziej efektywnie, ponieważ myślę, że byłoby możliwe wykonanie operacji odwrócenia w czasie O (1).

Właściwie właśnie zdałem sobie sprawę, że zrobienie tego spowodowałoby, że cała rzecz, o której mówię, może dlatego, że właśnie zdałem sobie sprawę, że struktura danych, którą miałem na myśli, pozwoliłaby uzyskać dostęp do elementów losowych w O (log n) i określić, czy wymaga odwrócenia w O (n ).

Randomsubsetsort.

Mając tablicę n elementów, wybierz każdy element z prawdopodobieństwem 1 / n, losuj te elementy i sprawdź, czy tablica jest posortowana. Powtarzaj, aż posortowane.

Oczekiwany czas pozostawia czytelnikowi jako ćwiczenie.