Apa algoritma penyortiran yang paling tidak jelas yang Anda ketahui? [Tutup]

Saya baru saja membaca tentang cyclesort melalui posting blog sortvis.org. Ini mungkin yang paling tidak jelas yang pernah saya dengar sejauh ini, karena menggunakan matematika yang saya tidak kenal (mendeteksi siklus permutasi dari set integer).

Apa yang paling tidak jelas yang Anda tahu?

Pernah mendengar tentang Penyortiran Kesabaran ? Nah sekarang kamu sudah ...

Slowsort bekerja dengan melipatgandakan dan menyerah (bukan untuk membagi dan menaklukkan). Ini menarik karena terbukti merupakan algoritma penyortiran yang paling tidak efisien yang dapat dibangun (asimptotik, dan dengan pembatasan bahwa algoritma semacam itu, walaupun lambat, harus tetap sepanjang waktu bekerja menuju hasil).

Ini mengimbanginya dari bogosort karena dalam kasus terbaik, bogosort cukup efisien - yaitu, ketika array sudah diurutkan. Slowsort tidak “menderita” dari perilaku terbaiknya. Bahkan dalam kasus terbaiknya, ia masih memiliki runtime untuk ϵ > 0.

Ini kodesemu, diadaptasi dari artikel Wikipedia bahasa Jerman :

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)

Saya tidak tahu apakah ini dianggap tidak jelas, tetapi salah satu "algoritma" pengurutan yang paling konyol adalah Bogosort . Tautan dari halaman Bogosort juga menyenangkan.

Dan ada permata ini dari bagian "quantum bogo-sort".

Bisa dibilang, menciptakan 2 ^N semesta juga sangat intensif memori.

Hmmm ... bisa dibilang :-).

"Algoritma" tidak jelas lainnya adalah Intelligent Design Sort - tetapi tidak ada algoritma yang lebih cepat atau memiliki konsumsi memori lebih sedikit :)

Sleep Sort agak baru.

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

contoh penggunaan:

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

Saya pikir semacam gelembung akan menjadi jawaban yang salah dalam situasi ini juga

:)

Knuth Volume 3 ¹ , dalam jawaban untuk salah satu latihan, memberikan implementasi algoritma pengurutan tanpa nama yang pada dasarnya adalah kode golf kuno - jenis terpendek yang dapat Anda tulis dalam bahasa assembly MIX. Kode singkat tidak datang pada harga oh-so-minor kompleksitas O (N ³ ) meskipun ...

¹ Setidaknya dalam edisi yang lebih lama. Mengingat modifikasi untuk MIXAL untuk edisi baru, saya tidak yakin apakah itu masih ada, atau bahkan membuat sedikit sangat masuk akal lakukan di MIXAL asli.

Untuk kelas struktur data saya, saya harus (secara eksplisit) membuktikan kebenaran jenis Stooge . Ini memiliki waktu berjalan O (n ^ {log 3 / log 1.5}) = O (n ^ 2.7095 ...).

Saya tidak tahu apakah itu yang paling tidak jelas, tetapi spageti adalah salah satu yang terbaik dalam situasi di mana Anda dapat menggunakannya.

Salah satu buku Knuth asli, "Sorting and Searching", memiliki lipatan tengah yang menggambarkan proses yang mengurutkan file tape tanpa menggunakan hard disk. Saya pikir itu menggunakan enam tape drive, dan secara eksplisit menunjukkan ketika masing-masing dibaca maju, membaca mundur, memutar balik, atau menganggur. Hari ini adalah monumen untuk teknologi yang usang.

Saya pernah melakukan semacam gelembung register vektor dalam assembler CRAY. Mesin memiliki instruksi shift ganda, yang memungkinkan Anda untuk menggeser isi register vektor naik / turun dengan satu kata. Letakkan setiap titik lainnya dalam dua register vektor, maka Anda bisa melakukan semacam gelembung penuh tanpa harus membuat referensi memori lain sampai Anda selesai. Kecuali untuk sifat bubble ** N ** 2 itu efisien.

Saya juga pernah perlu melakukan semacam floating point dari vektor panjang 4 secepat mungkin untuk satu jenis. Melakukannya dengan pencarian tabel (bit tanda A2-A1 adalah satu bit, tanda A3-A1 membentuk bit lain ..., lalu Anda mencari vektor permutasi dalam sebuah tabel. Itu sebenarnya solusi tercepat yang bisa saya buat dengan. Tidak bekerja dengan baik pada arsitektur modern, unit mengambang dan bilangan bulat terlalu terpisah.

Google Code Jam memiliki masalah tentang algoritme yang disebut Gorosort, yang saya pikir mereka temukan untuk masalahnya.

Goro memiliki 4 lengan. Goro sangat kuat. Anda tidak macam-macam dengan Goro. Goro perlu mengurutkan array N bilangan bulat yang berbeda. Algoritma bukanlah kekuatan Goro; kekuatan adalah kekuatan Goro. Rencananya Goro adalah menggunakan jari pada dua tangannya untuk menahan beberapa elemen array dan memukul meja dengan tinju ketiga dan keempatnya sekuat mungkin. Ini akan membuat elemen-elemen yang tidak aman dari array terbang ke udara, dikocok secara acak, dan jatuh kembali ke lokasi array yang kosong.

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

Jangan ingat namanya, tapi itu pada dasarnya

while Array not sorted

  rearrange the array in a random order

Semacam shell

Mungkin algoritme itu sendiri tidak begitu jelas, tetapi siapa yang dapat menyebutkan implementasi yang sebenarnya digunakan dalam praktik? Saya bisa!

TIGCC (kompiler berbasis GCC untuk kalkulator grafik TI-89/92 / V200) menggunakan Shell sort untuk qsortimplementasi di pustaka standarnya:

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

Shell sort dipilih untuk quicksort agar ukuran kode tetap rendah. Meskipun kompleksitas asimptotiknya lebih buruk, TI-89 tidak memiliki banyak RAM (190K, minus ukuran program dan ukuran total dari setiap variabel yang tidak diarsipkan), jadi agak aman untuk mengasumsikan bahwa jumlah item akan rendah.

Implementasi yang lebih cepat ditulis setelah saya mengeluh karena terlalu lambat dalam program yang saya tulis. Ia menggunakan ukuran celah yang lebih baik, bersama dengan optimisasi perakitan. Itu dapat ditemukan di sini: qsort.c