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


178

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!))?


10
Ile bogomipów na bogosort? Dociekliwe umysły chcą wiedzieć.
zombat

13
Aby wyjaśnić, czy wykluczasz trywialny przypadek, w którym najlepszy przypadek wydajności to O (∞)?
tloflin


6
Słyszałem, że gatunek małpy jest również znany jako „gatunek pijaka”, nazwa, która wydaje mi się znacznie bardziej sugestywna.
Matteo Italia

6
@Matteo Italia - lub można to nazwać „Toddler Sort”, co może potwierdzić każdy, kto ma 2 lata.
Martin Capodici

Odpowiedzi:


442

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!


94
Znany również jako „Sortowanie według założeń”: Załóżmy, że lista jest posortowana, wróć!
BioGeek

42
+100 - ta odpowiedź składa się z 100% czystej wygranej.
womp

11
Hej! Nie zapomnij o „sortowaniu niezdecydowanym” (znanym również jako „sortowanie Schrodingera” lub „sortowanie kwantowe”), w którym lista może być sortowana lub nie, jednak sprawdzenie jej pokaże, czy tak jest. Oto moja próba realizacja: void quantum_sort (void *b, size_t n, size_t s, int (*c)(const void *, const void*)) { if (rand () % 2) qsort (b, n, s, c); }.
Joe D

6
Powinniśmy "This is the best of all posibble worlds because it is the world that is, and so in the best possible world the array would already be sorted!"
nazwać

2
Na przykład witam naszego nowego zwierzchnika przydziału. Witajcie sortownika!
Bryson

299

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”?


39
Zakładam, że można wykorzystać promienie kosmiczne do udowodnienia poprawności tego algorytmu.
ghord,

1
Jakie jest w tym duże O? O(2^N)?
Mooing Duck,

12
@MooingDuck: Nie sądzę, żeby to faktycznie miało duże O.
Keith Thompson,

5
@MooingDuck: Ściśle mówiąc, jeśli to nie zakończy, to nie jest algorytmem, zgodnie z tym, czego nauczyli mnie na studiach i z artykułu w Wikipedii .
Keith Thompson,

7
@Olathe: Problem z zatrzymaniem mówi, że nie możemy określić dla wszystkich programów, czy się zatrzymują, ale istnieje wiele programów, dla których możemy to określić. Wiemy, że Quicksort i Bubblesoft zatrzymują się i wiemy, że to algorytmy.
Keith Thompson

133

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.


42
Ale czas przestaje istnieć we wszechświecie, który właśnie zniszczyłeś. Zatem obserwator we wszechświecie, którego jeszcze nie sprawdziłeś, nie będzie w stanie stwierdzić, jaka część algorytmu została wykonana. Zatem ten algorytm zawsze zajmuje O (1) czasu, ponieważ poprzednie zniszczenia wszechświata już nie istnieją.
Barry Brown

12
Tak, w jedynym wszechświecie, który obserwuje posortowaną listę, wykonanie zajęło O (n) czasu - nie ma znaczenia, ile czasu zajęło to w innych wszechświatach.
Nick Johnson,

19
Ten algorytm ma jednak znacznie większy problem. Załóżmy, że raz na 10 miliardów razy błędnie stwierdzisz, że lista jest posortowana, gdy tak nie jest. Jest ich 20! sposoby sortowania listy 20-elementowej. Po sortowaniu pozostałe wszechświaty będą tymi, w których lista została poprawnie posortowana, a 2,4 miliona wszechświatów, w których algorytm błędnie uznał, że lista została posortowana poprawnie. A więc mamy tutaj algorytm do masowego powiększania wskaźnika błędów maszyny.
Nick Johnson,

10
To oczywiście najlepszy algorytm sortowania, a nie najgorszy.
Boann

11
Niezastosowanie się do rady Beetle'a może spowodować zniszczenie wszystkich wszechświatów.
CrashCodes

60

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.


3
To wydaje się być O(N)porządek, ale w rzeczywistości jest ograniczony jednak narzędziach OS timerów.
Mooing Duck,

7
Jakkolwiek ją pokroisz, prawdopodobnie wykazuje lepszy wzrost niż bogosort.
Mooing Duck,

8
Widzę tam stan wyścigu.

5
Możesz zmienić opcję na, sleep "$1"aby sleep "0.$(printf "%010d" $1)"znacznie poprawić wydajność. time ./sleepsort.sh 8864569 7następnie działa w 0,009 s na moim laptopie.
Sam Kellett

1
Działa to w złożoności O (N) (zależnej oczywiście od implementacji timera), jest to proste sortowanie wiadra w innej formie.
Qwerty01

60

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ą.


50

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)


4
Bardziej interesujący do analizy jest przypadek średni , który jest ...?
Mooing Duck,

4
Jak mówią wszystkie najlepsze podręczniki, jest to ćwiczenie dla czytelnika!
Daniel

40
Mooing Duck: O (czasami)
Ilya O.

1
@MooingDuck to musimy znać liczność typu elementu i dystrybucji używanej do generowania losowych elementów w losowych tablicach.
Wyświetlana nazwa

5
Złożoność wynosi O (N! * Z ^ N), gdzie Z jest rozmiarem zbioru możliwych wartości, a N jest długością tablicy.
jakubiszon

30

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

14
Ale potrzeba O (n), aby sprawdzić, czy jest posortowane, więc możesz uzyskać O (n * n!)
erikkallen

3
@erikkallen: Z pewnością możemy wymyślić algorytm do weryfikacji sortowania, który jest gorszy niż O (n). Na przykład dla każdego elementu tablicy sprawdź, czy jest większy niż wszystkie poprzednie, podobnie jak działa sortowanie przez wstawianie. To algorytm O (n ^ 2) i jestem pewien, że po krótkiej przemyśleniu mógłbym wymyślić gorszy.
David Thornley,

7
@David Thornley: następujący algorytm sprawdzający może wykazywać tego samego ducha co bogosort: wybierz dwa losowe elementy, sprawdź, czy ten z mniejszym indeksem jest mniejszy lub równy temu z większym indeksem, a następnie powtórz. Zachowaj kwadratową macierz bitową, aby zobaczyć, które kombinacje zostały już sprawdzone. Oczywiście sprawdzenie tej macierzy można by też zrobić w chodzie losowym ...
Svante

19

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.


5
Święta Matko Kodeksu. Myślę, że możemy nawet zrobić krótki film Bogolplex.
MrKekson

19

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).


19

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 .


1
świetna odpowiedź. smutne, że nie ma widoczności
swyx

16

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


Drugi jest prawie odpowiednikiem rodzaju bozo. Pierwsza jest jednak sprytna.
Mooing Duck,

1
Pierwsza to Miracle Sort.
Karol

14

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; }
}

5
I podoba mi się pomysł, że algorytm ten jest zaprojektowany, aby nie zakończyć „przed śmiercią cieplnej wszechświata dla każdej listy spore”
A.Grandt

10

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.


9
Nie, to jest gorsze, ponieważ nie ma szans na powodzenie. Jak karty katalogowe trafiłyby do twojej kuchni? Wieją na zewnątrz. To się nazywa sortowanie tyłków.
Patrick Karcher

Myślę, że ma na myśli wyrzucenie kart w powietrze na zewnątrz , a następnie sprawdzenie podłogi w środku , gdzie na pewno nie będzie żadnych kart. Chociaż nie jest to „nazwany” algorytm… jest z pewnością gorszy!
womp

10
@Patrick Quantum Tuneling.
kennytm

8
@KennyTM. Tak naprawdę przyszło mi do głowy. Istnieje bardzo mała, ale niezerowa szansa, że ​​jakikolwiek obiekt może zniknąć i pojawić się ponownie w jakimkolwiek innym punkcie wszechświata. Myślę, że może się to przytrafić tysiącowi kart indeksowych. . . Oi. Cholera, mój algorytm jest wadliwy . Naprawię to . . .
Patrick Karcher,

3
To tak, jakby mieć herbatę i nie mieć herbaty w tym samym czasie. Albo podróże kosmiczne wykorzystujące nieskończony napęd nieprawdopodobieństwa.
Barry Brown

9

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).


8

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


38
Nieskończoność + 1. Jinx, bez powrotu.
zombat

24
Nie dla ekstremalnie dużych wartości 1;)
zombat

8
To, co naprawdę uderza mnie w koncepcję nieskończoności, to fakt, że możesz mieć różne „rozmiary” nieskończoności. Rozważmy na przykład zbiór wszystkich liczb całkowitych - ma on nieskończony rozmiar. Rozważmy teraz zbiór wszystkich parzystych liczb całkowitych - ma on również nieskończony rozmiar, ale jest też wyraźnie o połowę mniejszy od pierwszego zbioru. Obie nieskończone, ale różne rozmiary. Niesamowite. Pojęcie „rozmiaru” po prostu zawodzi w kontekście nieskończoności.
zombat

4
@zombat: Mówisz o liczności, a nie nieskończoności jako symbolu wskazującym na trend na prawdziwej linii / złożonej płaszczyźnie.
kennytm

18
@zombat. Rozmiar zbioru parzystych liczb całkowitych jest taki sam jak rozmiar zbioru liczb całkowitych, o czym świadczy fakt, że można je umieścić w korespondencji jeden do jednego. Teraz jest więcej liczb rzeczywistych niż liczb całkowitych, jak po raz pierwszy pokazał Cantor.
David Thornley,

5

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.


5

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.

4

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 2 ) 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ć :)


3

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.


3
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);
}

2

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; }
        }
}

2

Podwójny bogosort

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


1

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.

1

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 (;;);
}

1

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 ).


1

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.