Apakah ada algoritma penyortiran yang lebih buruk daripada Bogosort (alias Monkey Sort)? [Tutup]

Rekan kerja saya membawa saya kembali ke masa-masa Universitas saya dengan diskusi tentang penyortiran algoritma pagi ini. Kami mengenang tentang favorit kami seperti StupidSort , dan salah satu dari kami yakin kami telah melihat semacam algoritma itu O(n!). Itu membuat saya mulai mencari-cari algoritma penyortiran "terburuk" yang bisa saya temukan.

Kami mendalilkan bahwa jenis acak sepenuhnya akan sangat buruk (yaitu mengacak elemen - apakah itu dalam urutan? Tidak? Mengacak lagi), dan saya melihat sekeliling dan menemukan bahwa itu tampaknya disebut BogoSort, atau Macam Monyet, atau kadang-kadang hanya Urutan Acak .

Sortir Monyet tampaknya memiliki kinerja kasus terburuk O(∞), kinerja kasus terbaik O(n), dan kinerja rata-rata O(n·n!).

Apa algoritma pengurutan yang diterima saat ini dengan kinerja pengurutan rata-rata terburuk (dan karena itu menjadi lebih buruk daripada O(n·n!))?

Dari halaman Algoritma Esoterik David Morgan-Mar : Urutan Desain Cerdas

pengantar

Sorting desain cerdas adalah algoritma pemilahan berdasarkan teori desain cerdas.

Deskripsi Algoritma

Kemungkinan daftar input asli berada dalam urutan persisnya adalah 1 / (n!). Ada kemungkinan kecil hal ini sehingga jelas tidak masuk akal untuk mengatakan bahwa ini terjadi secara kebetulan, jadi pasti secara sadar dimasukkan ke dalam urutan itu oleh Penyortir yang cerdas. Karena itu aman untuk berasumsi bahwa itu sudah diurutkan secara optimal dalam beberapa cara yang melampaui pemahaman fana kita yang naif tentang "tatanan naik". Setiap upaya untuk mengubah urutan agar sesuai dengan prasangka kita sendiri sebenarnya akan membuatnya kurang diurutkan.

Analisis

Algoritma ini konstan dalam waktu, dan mengurutkan daftar di tempat, tidak memerlukan memori tambahan sama sekali. Bahkan, itu bahkan tidak memerlukan semua hal yang mencurigakan dari teknologi komputer. Puji Penyortir!

Umpan balik

Gary Rogers menulis:

Menjadikan penyortiran konstan dalam waktu menyangkal kekuatan Penyortir. Penyortir ada di luar waktu, sehingga penyortir tidak akan lekang oleh waktu. Membutuhkan waktu untuk memvalidasi jenis ini akan mengurangi peran Penyortir. Jadi ... jenis khusus ini cacat, dan tidak dapat dikaitkan dengan 'Penyortir'.

Bidaah!

Bertahun-tahun yang lalu, saya menemukan MiracleSort (tetapi tidak pernah benar-benar diterapkan).

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

Akhirnya, partikel alfa yang membalik bit dalam chip memori akan menghasilkan jenis yang sukses.

Untuk keandalan yang lebih besar, salin array ke lokasi terlindung, dan periksa array berpotensi diurutkan terhadap yang asli.

Jadi, bagaimana Anda memeriksa array yang berpotensi diurutkan terhadap yang asli? Anda cukup mengurutkan setiap array dan memeriksa apakah cocok. MiracleSort adalah algoritma yang jelas digunakan untuk langkah ini.

EDIT: Sebenarnya, ini bukan algoritma, karena tidak dijamin akan berakhir. Apakah "bukan suatu algoritma" memenuhi syarat sebagai "algoritma yang lebih buruk"?

Bogumort Kuantum

Algoritma pengurutan yang mengasumsikan bahwa interpretasi mekanika kuantum banyak dunia adalah benar:

1. Pastikan daftar diurutkan. Jika tidak, hancurkan jagat raya.

Pada akhir algoritme, daftar akan diurutkan dalam satu-satunya alam semesta yang tersisa. Algoritma ini membutuhkan waktu kasus terburuk O (N) dan kasus rata-rata O (1). Faktanya, jumlah rata-rata perbandingan yang dilakukan adalah 2: ada kemungkinan 50% bahwa alam semesta akan dihancurkan pada elemen kedua, peluang 25% bahwa itu akan dihancurkan pada elemen ketiga, dan seterusnya.

Saya terkejut belum ada yang menyebutkan sleepsort ... Atau belumkah saya menyadarinya? Bagaimanapun:

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

contoh penggunaan:

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

Dalam hal kinerja itu mengerikan (terutama contoh kedua). Menunggu hampir 3,5 bulan untuk mengurutkan 2 angka agak buruk.

Sortasi Jingle, seperti dijelaskan di sini .

Anda memberikan setiap nilai dalam daftar Anda kepada anak yang berbeda pada hari Natal. Anak-anak, sebagai manusia yang mengerikan, akan membandingkan nilai hadiah mereka dan menyortir diri mereka sendiri.

Saya punya dosen yang pernah menyarankan membuat array acak, memeriksa apakah itu diurutkan dan kemudian memeriksa apakah datanya sama dengan array yang akan diurutkan.

Kasus terbaik O (N) (bayi pertama kali!) Kasus terburuk O (Tidak pernah)

Jika Anda mempertahankan algoritme dengan cara apa pun, O(n!)adalah batas atas terburuk yang dapat Anda capai.

Karena memeriksa setiap kemungkinan permutasi dari satu set yang akan diurutkan akan mengambil n!langkah - langkah, Anda tidak bisa mendapatkan yang lebih buruk dari itu.

Jika Anda melakukan langkah-langkah lebih dari itu maka algoritma tidak memiliki tujuan yang sangat berguna. Belum lagi algoritma penyortiran sederhana berikut dengan O(infinity):

list = someList
while (list not sorted):
    doNothing

Bogobogosort. Ya, itu hal. ke Bogobogosort, Anda Bogosort elemen pertama. Periksa untuk melihat apakah satu elemen diurutkan. Menjadi satu elemen, itu akan menjadi. Kemudian Anda menambahkan elemen kedua, dan Bogosort keduanya sampai diurutkan. Kemudian Anda menambahkan satu elemen lagi, lalu Bogosort. Lanjutkan menambahkan elemen dan Melakukan Bogosorting sampai Anda selesai melakukan semua elemen. Ini dirancang untuk tidak pernah berhasil dengan daftar besar sebelum kematian panas alam semesta.

Anda harus melakukan penelitian di bidang Algoritma Pessimal dan Analisis Simpleksitas yang menarik . Para penulis ini bekerja pada masalah mengembangkan semacam dengan kasus terbaik pessimal (kasus terbaik bogosort Anda adalah Omega (n), sementara slowsort (lihat kertas) memiliki kompleksitas waktu kasus terbaik non-polinomial).

Ada semacam yang disebut bogobogosort. Pertama, ia memeriksa 2 elemen pertama, dan bogosort mereka. Selanjutnya periksa 3 pertama, bogosort mereka, dan sebagainya.

Jika daftar ini rusak, kapan saja, akan dimulai lagi dengan melakukan bogosort pada 2 yang pertama lagi. Bogosort biasa memiliki kompleksitas rata-rata O(N!), algoritma ini memiliki kompleksitas rata-rataO(N!1!2!3!...N!)

Sunting : Untuk memberi Anda gambaran tentang seberapa besar angka ini, untuk 20elemen, algoritma ini membutuhkan rata-rata 3.930093*10^158 tahun , jauh di atas panas yang diusulkan kematian alam semesta (jika terjadi) 10^100 tahun ,

sedangkan pengurutan penggabungan membutuhkan waktu sekitar .0000004 detik , pengurutan gelembung .0000016 detik , dan bogosort membutuhkan waktu 308 bertahun - tahun , 139 berhari-hari , 19 berjam-jam , 35 menit , 22.306 detik , dengan asumsi satu tahun adalah 365,222 hari dan komputer melakukan 250.000.000 32 bit operasi integer per detik.

Sunting2 : Algoritma ini tidak selambat jenis keajaiban "algoritma", yang mungkin, seperti jenis ini, akan membuat komputer tersedot ke dalam lubang hitam sebelum berhasil mengurutkan 20 elemtnts, tetapi jika ya, saya akan memperkirakan kompleksitas rata-rata 2^(32(the number of bits in a 32 bit integer)*N)(the number of elements)*(a number <=10^40) bertahun - tahun ,

karena gravitasi mempercepat chip alpha yang bergerak, dan ada 2 ^ N status, yaitu 2^640*10^40, atau sekitar 5.783*10^216.762162762 bertahun - tahun , meskipun jika daftar mulai diurutkan, kompleksitasnya hanya akan O(N), lebih cepat daripada menggabungkan jenis, yang hanya N log N bahkan pada kasus terburuk.

Sunting3 : Algoritme ini sebenarnya lebih lambat daripada jenis keajaiban karena ukurannya menjadi sangat besar, katakan 1000, karena algoritma saya akan memiliki jangka waktu 2.83*10^1175546 bertahun - tahun , sedangkan algoritma jenis keajaiban akan memiliki jangka waktu 1.156*10^9657 bertahun - tahun .

Inilah 2 macam saya datang dengan teman sekamar saya di perguruan tinggi

1) Periksa pesanan 2) Mungkin keajaiban terjadi, buka 1

dan

1) periksa apakah sudah beres, jika tidak 2) masukkan setiap elemen ke dalam sebuah paket dan bangkit kembali dari server yang jauh ke diri Anda sendiri. Beberapa paket tersebut akan kembali dalam urutan yang berbeda, jadi buka 1

Selalu ada Bogobogosort (Bogoception!). Ia melakukan Bogosort pada himpunan bagian yang semakin besar dari daftar, dan kemudian mulai dari awal lagi jika daftar tersebut tidak pernah diurutkan.

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 Masukkan barang-barang Anda untuk diurutkan pada kartu indeks
2 Lemparkan ke udara pada hari yang berangin, satu mil dari rumah Anda.
2 Lemparkan mereka ke api unggun dan pastikan mereka benar-benar hancur.
3 Periksa lantai dapur Anda untuk pemesanan yang benar.
4 Ulangi jika ini bukan urutan yang benar.

Scenerio kasus terbaik adalah O (∞)

Sunting di atas berdasarkan pengamatan cerdik oleh KennyTM.

"Kamu ingin jadi apa?" menyortir

1. Catat waktu sistem.
2. Sortir menggunakan Quicksort (atau apa pun yang masuk akal), menghilangkan swap terakhir.
3. Catat waktu sistem.
4. Hitung waktu yang dibutuhkan. Diperpanjang aritmatika presisi adalah persyaratan.
5. Tunggu waktu yang dibutuhkan.
6. Lakukan swap terakhir.

Tidak hanya dapat mengimplementasikan nilai O (x) yang mungkin pendek dari tak terbatas, waktu yang diperlukan terbukti benar (jika Anda bisa menunggu selama itu).

Tidak ada yang lebih buruk daripada tak terbatas.

Bozo sort adalah algoritma terkait yang memeriksa apakah daftar diurutkan dan, jika tidak, menukar dua item secara acak. Ini memiliki penampilan kasus terbaik dan terburuk yang sama, tetapi saya secara intuitif berharap kasus rata-rata lebih lama dari Bogosort. Sulit untuk menemukan (atau menghasilkan) data apa pun tentang kinerja algoritma ini.

Segmen π

Asumsikan π berisi semua kemungkinan kombinasi angka hingga. Lihat pertanyaan math.stackexchange

1. Tentukan jumlah digit yang dibutuhkan dari ukuran array.
2. Gunakan segmen π tempat sebagai indeks untuk menentukan cara memesan ulang array. Jika segmen melebihi batas ukuran untuk array ini, sesuaikan offset imal desimal dan mulai lagi dari awal.
3. Periksa apakah array yang dipesan ulang sudah diurutkan. Jika woot, sesuaikan offset dan mulai lagi dari awal.

Kinerja kasus terburuk O (∞) bahkan mungkin tidak menjadikannya suatu algoritma menurut beberapa orang .

Algoritma hanyalah serangkaian langkah dan Anda selalu dapat melakukan yang lebih buruk dengan mengubah sedikit untuk mendapatkan hasil yang diinginkan dalam lebih banyak langkah daripada sebelumnya. Seseorang dapat dengan sengaja menaruh pengetahuan tentang jumlah langkah yang diambil ke dalam algoritma dan membuatnya berhenti dan menghasilkan output yang benar hanya setelah Xsejumlah langkah telah dilakukan. Itu Xbisa sangat urutan O (n ² ) atau O (n ^n! ) Atau apa pun algoritma yang ingin dilakukan. Itu akan secara efektif meningkatkan batas kasus terbaik dan rata-rata.

Tetapi skenario terburuk Anda tidak dapat diatapi :)

Algoritma pengurutan lambat favorit saya adalah jenis antek:

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

Kompleksitas kasus terburuk adalah O(n^(log(3) / log(1.5))) = O(n^2.7095...).

Algoritma pengurutan lambat lainnya sebenarnya bernama slowsort!

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

Yang ini mengambil O(n ^ (log n))kasus terbaik ... bahkan lebih lambat dari antek.

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

Halaman ini adalah bacaan menarik tentang topik ini: http://home.tiac.net/~cri_d/cri/2001/badsort.html

Favorit pribadi saya adalah Tom Duff's sillysort:

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

Bogosort ganda

Bogosort dua kali dan bandingkan hasilnya (hanya untuk memastikan itu diurutkan) jika tidak melakukannya lagi

Anda dapat membuat algoritma pengurutan apa pun lebih lambat dengan menjalankan langkah "apakah diurutkan" secara acak. Sesuatu seperti:

1. Buat array booleans dengan ukuran yang sama dengan array yang Anda sortir. Jadikan semuanya salah.
2. Jalankan iterasi bogosort
3. Pilih dua elemen acak.
4. Jika dua elemen diurutkan dalam kaitannya dengan satu sama lain (i <j && array [i] <array [j]), tandai indeks keduanya pada array boolean menjadi true. Secara berlebihan, mulailah dari awal.
5. Periksa apakah semua boolean dalam array benar. Jika tidak, kembali ke 3.
6. Selesai

Ya, SimpleSort, secara teori ini berjalan di O(-1)bagaimanapun ini setara denganO(...9999) yang pada gilirannya setara dengan O (∞ - 1), yang seperti itu juga setara dengan O (∞). Berikut ini contoh implementasi saya:

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

Satu yang baru saja saya kerjakan melibatkan memilih dua poin acak, dan jika mereka berada di urutan yang salah, membalikkan seluruh subrange di antara mereka. Saya menemukan algoritma di http://richardhartersworld.com/cri_d/cri/2001/badsort.html , yang mengatakan bahwa case rata-rata mungkin ada di sekitar O (n ^ 3) atau O (n ^ 2 log n) ( dia tidak begitu yakin).

Saya pikir mungkin untuk melakukannya lebih efisien, karena saya pikir mungkin untuk melakukan operasi pembalikan dalam O (1) waktu.

Sebenarnya, saya baru sadar bahwa melakukan itu akan membuat semua yang saya katakan mungkin karena saya baru menyadari bahwa struktur data yang ada dalam pikiran saya akan menempatkan mengakses elemen acak di O (log n) dan menentukan apakah perlu membalikkan pada O (n ).

Randomsubsetsort.

Diberikan array elemen n, pilih setiap elemen dengan probabilitas 1 / n, acak elemen-elemen ini, dan periksa apakah array diurutkan. Ulangi sampai diurutkan.

Waktu yang diharapkan dibiarkan sebagai latihan untuk pembaca.