Jumlah perbandingan yang dibutuhkan paling sedikit untuk mengurutkan (memesan) 5 elemen

Temukan jumlah perbandingan paling sedikit yang diperlukan untuk mengurutkan (memesan) lima elemen dan menyusun algoritma yang mengurutkan elemen-elemen ini menggunakan jumlah perbandingan ini.

Solusi : Ada 5! = 120 hasil yang mungkin. Oleh karena itu pohon biner untuk prosedur penyortiran akan memiliki setidaknya 7 level. Memang, ≥ 120 menyiratkan jam ≥ 7. Tetapi 7 perbandingan tidak cukup. Jumlah perbandingan paling sedikit yang diperlukan untuk mengurutkan (memesan) lima elemen adalah 8.$2^h$$h$

Berikut adalah pertanyaan saya yang sebenarnya: Saya menemukan sebuah algoritma yang melakukannya dalam 8 perbandingan tetapi bagaimana saya bisa membuktikan bahwa itu tidak dapat dilakukan dalam 7 perbandingan?

Solusinya salah. Demuth [1; via 2, dtk. 5.3.1] menunjukkan bahwa lima nilai dapat diurutkan menggunakan hanya tujuh perbandingan, yaitu bahwa batas bawah "teori informasi" ketat dalam hal ini.

Jawabannya adalah metode yang disesuaikan dengan , bukan algoritma umum. Ini juga tidak terlalu bagus. Inilah garis besarnya:$n=5$

1. Sortir dua pasangan pertama.

2. Memesan pasangan dengan elemen yang lebih besar.

   Sebut hasilnya ; kita tahu a < b < d dan c < d .$[a,b,c,d,e]$$a<b<d$$c<d$

3. Masukkan ke [ a , b , d ] .$e$$[a,b,d]$

4. Masukkan ke hasil langkah 3.$c$

Langkah pertama jelas membutuhkan dua perbandingan, yang kedua hanya satu. Dua langkah terakhir masing-masing mengambil dua perbandingan; kita memasukkan ke dalam daftar tiga elemen dalam kedua kasus (untuk langkah 4., perhatikan bahwa kita tahu dari bahwa c lebih kecil dari elemen terakhir dari daftar yang ada di tangan) dan bandingkan dengan elemen tengah terlebih dahulu. Itu membuat total tujuh perbandingan.$c<d$$c$

Karena saya tidak melihat bagaimana cara menulis pseudocode "bagus" ini, lihat di sini untuk implementasi yang teruji (dan mudah-mudahan dapat dibaca).

1. Ph.D. tesis (Universitas Stanford) oleh HB Demuth (1956)

   Lihat juga Penyortiran Data Elektronik oleh HB Demuth (1985)

2. Penyortiran dan Pencarian oleh Donald E. Knuth; Seni Pemrograman Komputer Vol. 3 (2nd ed, 1998)

$\log(n!)$$n$$<$$>$$n!$$\log(5!) \approx 6.91$

$5!= 120$$2^7= 128$

Ini bukan kode yang cantik atau pendek, dan Anda mungkin harus menggunakan metode pembuatan kode untuk membuat pohon keputusan dan bertukar daripada mengkodekannya dengan tangan, tetapi ini berfungsi; dan terbukti bekerja untuk setiap permutasi yang memungkinkan dari 5 item, dengan demikian membuktikan Anda dapat mengurutkan 5 item dalam tidak lebih dari 7 perbandingan.

saya sedang berpikir quicksort. Anda memilih sebagai pivot elemen yang kebetulan menjadi elemen tengah. bandingkan pivot dengan 4 item yang tersisa yang menghasilkan dua tumpukan untuk disortir. masing-masing tumpukan dapat disortir dalam 1 perbandingan. kecuali saya telah melakukan kesalahan yang mengerikan, 5 item sepenuhnya disortir hanya dalam 6 perbandingan dan saya pikir itu adalah perbandingan paling sedikit mutlak yang diperlukan untuk melakukan pekerjaan itu. pertanyaan awal adalah menemukan perbandingan jumlah paling sedikit untuk mengurutkan 5 elemen.

Jika Anda dapat menguji algoritme, ujilah pada semua kombinasi angka. Jika Anda memiliki banyak angka, uji banyak kombinasi acak. Tidak tepat, tetapi lebih cepat dari semua kombinasi.

Minimal
a <b <c = 2
a <b <c <d = 3
a <b <c <d <e = 4

Maksimal
3 ^ 3
4 ^ 4
5 ^ 5

Masukkan ke tengah gunakan 3-6 untuk 4 angka.
Penggabungan menggunakan 4-5 untuk 4 angka.
Minimal dibandingkan dengan wiki adalah 5 untuk 4 angka :) Untuk 5 adalah 7. Anda menggunakan 8, masih sangat banyak.
https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
Jika Anda tahu semua sebelum perbandingan, Anda bisa turun dengan perbandingan. Rata-rata saya untuk 4 angka adalah 3,96 / 1024 semua kombinasi.