Jaki jest najbardziej niejasny algorytm sortowania, jaki znasz? [Zamknięte]

Właśnie przeczytałem o cyclesort za pośrednictwem postu na blogu sortvis.org. Jest to prawdopodobnie najbardziej niejasny, o jakim dotąd słyszałem, ponieważ wykorzystuje matematykę, której nie znam (wykrywanie cykli w permutacjach zbiorów liczb całkowitych).

Jaki jest najbardziej niejasny, jaki znasz?

Słyszałeś kiedyś o sortowaniu cierpliwości ? Cóż, teraz masz ...

Slowsort działa przez pomnożenie i poddanie się (w przeciwieństwie do dzielenia i podbijania). Jest to interesujące, ponieważ jest to prawdopodobnie najmniej wydajny algorytm sortowania, który można zbudować (asymptotycznie i z zastrzeżeniem, że taki algorytm, choć powolny, musi cały czas dążyć do osiągnięcia rezultatu).

To równoważy go z bogosortem, ponieważ w najlepszym przypadku bogosort jest dość wydajny - mianowicie, gdy tablica jest już posortowana. Slowsort nie „cierpi” na takie najlepsze zachowanie. Nawet w najlepszym przypadku nadal ma czas działania dla ϵ > 0.

Oto jego pseudokod, zaadaptowany z niemieckiego artykułu w Wikipedii :

function slowsort(A, i, j):
  if i >= j: return

  m = (i + j) / 2
  slowsort(A, i, m)
  slowsort(A, m + 1, j)

  if A[j] < A[m]:
    swap(A[j], A[m])

  slowsort(A, i, j - 1)

Nie wiem, czy liczy się to jako niejasne, ale jednym z najbardziej absurdalnych „algorytmów” sortowania jest Bogosort . Linki na stronie Bogosort też są fajne.

I jest ten klejnot z sekcji „sortowanie bogactw kwantowych”.

Prawdopodobnie tworzenie 2 ^N wszechświatów wymaga również dużej ilości pamięci.

Hmmm ... można tak powiedzieć :-).

Kolejnym niejasnym „algorytmem” jest Inteligentne sortowanie projektów - ale żaden algorytm nie jest szybszy lub ma mniejsze zużycie pamięci :)

Sortowanie snu jest raczej nowatorskie.

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

przykładowe użycie:

    ./sleepsort.bash 5 3 6 3 6 3 1 4 7

Myślę, że rodzaj bąbelków byłby również złą odpowiedzią w tej sytuacji

:)

Knuth Tom 3 ¹ , w odpowiedzi na jedno z ćwiczeń, przedstawia implementację bezimiennego algorytmu sortowania, który jest w zasadzie starożytnym golfem kodowym - najkrótszym rodzajem, jaki można napisać w asemblerze MIX. Krótki kod jest dostępny w tak nieistotnej cenie złożoności O (N ³ ) ...

¹ Przynajmniej w starszych wersjach. Biorąc pod uwagę modyfikacje MIXAL-a dla nowej edycji, nie jestem pewien, czy nadal tam jest, czy nawet nie ma najmniejszego sensu w oryginalnym MIXAL-u.

W mojej klasie struktur danych musiałem (wyraźnie) udowodnić poprawność sortowania Stooge . Ma czas działania O (n ^ {log 3 / log 1,5}) = O (n ^ 2,7095 ...).

Nie wiem, czy jest to najbardziej niejasne, ale rodzaj spaghetti jest jednym z najlepszych w sytuacjach, w których można go użyć.

Jedna z oryginalnych książek Knutha „Sortowanie i wyszukiwanie” miała środkowy rozkład, który przedstawiał proces sortowania pliku taśmy bez użycia dysku twardego. Myślę, że używał sześciu napędów taśmowych i wyraźnie pokazał, kiedy każdy był czytany do przodu, do tyłu, do tyłu lub bezczynnie. Dziś jest pomnikiem przestarzałej technologii.

Kiedyś zrobiłem sortowanie bąbelkowe rejestrów wektorowych w asemblerze CRAY. Maszyna miała instrukcję podwójnej zmiany, która pozwoliła na przesunięcie zawartości rejestru wektorowego w górę / w dół o jedno słowo. Umieść co drugi punkt w dwóch rejestrach wektorowych, abyś mógł wykonać pełne sortowanie bąbelkowe bez konieczności tworzenia kolejnego odniesienia do pamięci, dopóki nie skończysz. Z wyjątkiem natury sortowania bąbelkowego N ** 2 była ona wydajna.

Raz też musiałem zrobić jakikolwiek zmiennoprzecinkowy wektor długości 4 tak szybko, jak to możliwe dla pojedynczego sortowania. Zrobiłem to przez przeglądanie tabeli (bit znaku A2-A1 jest jednym bitem, znak A3-A1 tworzy kolejny bit ..., a następnie wyszukujesz wektor permutacji w tabeli. To było w rzeczywistości najszybsze rozwiązanie, jakie mogłem wymyślić z. Nie działa jednak dobrze na nowoczesnych architekturach, jednostki pływające i liczby całkowite są zbyt rozdzielone.

Google Code Jam miał problem z algorytmem o nazwie Gorosort, który, jak sądzę, wymyślił dla tego problemu.

Goro ma 4 ramiona. Goro jest bardzo silny. Nie zadzieraj z Goro. Goro musi posortować tablicę N różnych liczb całkowitych. Algorytmy nie są siłą Goro; siła jest siłą Goro. Plan Goro polega na użyciu palców na dwóch dłoniach, aby przytrzymać kilka elementów tablicy i uderzyć w stół trzecią i czwartą pięścią tak mocno, jak to możliwe. To sprawi, że niezabezpieczone elementy tablicy wylecą w powietrze, zostaną losowo przetasowane i spadną z powrotem w puste miejsca tablicy.

http://code.google.com/codejam/contest/dashboard?c=975485#s=p3

Nie pamiętam nazwy, ale było w zasadzie

while Array not sorted

  rearrange the array in a random order

Sortowanie w skorupkach

Może sam algorytm nie jest tak niejasny, ale kto może nazwać implementację, która faktycznie jest używana w praktyce? Mogę!

TIGCC (kompilator oparty na GCC dla kalkulatorów graficznych TI-89/92 / V200) używa sortowania Shell do qsortimplementacji w swojej standardowej bibliotece:

__ATTR_LIB_C__ void qsort(void *list, short num_items, short size, compare_t cmp_func)
{
  unsigned short gap,byte_gap,i,j;                
  char *p,*a,*b,temp;                       
  for (gap=((unsigned short)num_items)>>1; gap>0; gap>>=1)    // Yes, this is not a quicksort,
    {                                                         // but works fast enough...    
      byte_gap=gap*(unsigned short)size;
      for(i=byte_gap; i<((unsigned short)num_items)*(unsigned short)size; i+=size)
        for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap)
          {
            a=p; b=p+byte_gap;
            if(cmp_func(a,b)<=0) break;
            for(j=size;j;j--)
              temp=*a, *a++=*b, *b++=temp;
          }
    }
}

Wybrano sortowanie powłoki na rzecz szybkiego sortowania, aby utrzymać niski rozmiar kodu. Chociaż jego asymptotyczna złożoność jest gorsza, TI-89 nie ma dużo pamięci RAM (190 KB, minus rozmiar programu i całkowity rozmiar niezarchiwizowanych zmiennych), więc można bezpiecznie założyć, że liczba elementów będzie być nisko.

Szybsze wdrożenie zostało napisane po tym, jak narzekałem, że jest zbyt wolny w pisanym przeze mnie programie. Wykorzystuje lepsze rozmiary szczelin wraz z optymalizacjami montażu. Można go znaleźć tutaj: qsort.c