Quicksort menjelaskan kepada anak-anak

Tahun lalu, saya membaca makalah yang fantastis tentang "Mekanika Kuantum untuk Taman Kanak-Kanak" . Itu bukan kertas mudah.

Sekarang, saya ingin tahu bagaimana menjelaskan quicksort dengan kata-kata sesederhana mungkin. Bagaimana saya bisa membuktikan (atau paling tidak gelombang tangan) bahwa kompleksitas rata-rata adalah , dan apa kasus terbaik dan terburuk, untuk kelas taman kanak-kanak? Atau setidaknya di sekolah dasar?$O(n \log n)$

Pada intinya, Quicksort adalah ini:

1. Ambil item pertama.
2. Pindahkan segala sesuatu yang kurang dari item pertama itu ke kiri, semuanya lebih besar ke kanan (dengan asumsi urutan naik).
3. Perulangan di setiap sisi.

Saya pikir setiap anak berusia 4 tahun di planet ini dapat melakukan 1 dan 2. Rekursi ini mungkin membutuhkan sedikit penjelasan, tetapi seharusnya tidak terlalu sulit bagi mereka.

1. Ulangi di sisi kiri, abaikan kanan untuk saat ini (tapi ingat di mana tengahnya)
2. Terus ulangi dengan sisi kiri sampai Anda tidak mendapatkan apa-apa. Sekarang kembali ke sisi kanan terakhir yang Anda abaikan, dan ulangi prosesnya di sana.
3. Setelah Anda kehabisan sisi kanan dan kiri, Anda selesai.

Adapun kompleksitasnya, kasus terburuk seharusnya cukup mudah. Pertimbangkan saja array yang sudah diurutkan:

1 2 3 4
  2 3 4
    3 4
      4

Cukup mudah untuk melihat (dan membuktikan) bahwa ini .$\frac{1}{2}n^2$

Saya tidak terbiasa dengan bukti rata-rata, jadi saya tidak bisa membuat saran untuk itu. Anda bisa mengatakan bahwa dalam array yang tidak disortir dengan panjang probabilitas untuk memilih item terkecil atau terbesar adalah $l$ , jadi ...?$\frac{2}{n}$

Quicksort sebenarnya cukup mudah untuk dipahami, jika mereka memahami penghitungan dasar dan pembagian dengan 2. Membuat banyak kartu flash X, beri nomor 1 - X, dan kocok. Maka inilah penjelasannya:

OK, kami punya setumpuk kartu (misalkan 20) di sini. Kami ingin mengaturnya, jadi 1 adalah yang pertama, kemudian 2, kemudian 3, dan seterusnya. Inilah cara yang sangat cepat untuk melakukannya.

Pertama, mari kita pergi melalui dek ini dan membuat dua tumpukan darinya. Setengah dari 20 adalah 10, jadi apa pun yang lebih besar dari 10 masuk tumpukan ini di sebelah kanan, dan apa pun yang lebih kecil masuk tumpukan ini di sebelah kiri. (Pastikan untuk menunjukkan saat Anda pergi.)

Sekarang, mari kita lakukan hal yang sama dengan tumpukan yang lebih kecil. Apa setengah dari 10? (Seseorang berkata "lima!") Itu benar! Jadi apapun yang lebih besar dari 5 masuk tumpukan ini di sebelah kanan, dan apa pun yang lebih kecil masuk tumpukan ini di sebelah kiri.

Dan di sini, kita punya kelompok yang lebih besar dari 10. Jadi setengah dari 10 adalah 5, dan apa yang 10 ditambah 5? (Seseorang berkata "lima belas!") Itu benar! Jadi apapun yang lebih besar dari 15 masuk tumpukan ini di sebelah kanan, dan sesuatu yang lebih kecil dari 15 masuk tumpukan di sebelah kiri.

Dan sekarang tumpukannya semakin kecil sehingga Anda dapat dengan mudah melihatnya dan menertibkannya. Lihat, ini dia 2, 4, 5, 3, 1. Jadi kami hanya mengubah mereka seperti ini, dan Anda bisa lihat 1, 2, 3, 4, 5. Jadi mari kita lakukan hal yang sama dengan tumpukan lainnya, dan kemudian kita hanya mengatur tumpukan, dan lihat! Mereka dalam urutan 1 hingga 20!

Selamat. Anda baru saja mengajar banyak anak-anak prinsip-prinsip dasar dari algoritma quicksort adaptif! Anda bisa sedikit lebih dalam dari itu tergantung pada kematangan mental, tetapi melangkah lebih jauh dari titik ini membutuhkan pemahaman tentang logika formal.

Sedangkan untuk membuktikan kompleksitasnya, itu lebih sulit. Ini adalah salah satu hal yang memerlukan logika formal, dan mereka harus memahami prinsip dasar notasi O besar. Anda mungkin ingin menunda bagian itu pada awalnya.

Bagaimana dengan ini?

Ilmu Komputer Unplugged - Algoritma Penyortiran

Itu tidak cukup mencakup semua pertanyaan Anda, tapi ini awal yang baik.

Sumber daya lebih banyak tentang topik ini ditautkan di sini .

Mereka juga menyediakan video yang menjelaskan algoritma pengurutan (termasuk quicksort) di sini . Video ini sangat membantu memahami perbedaan antara berbagai algoritma penyortiran untuk anak-anak muda.

Lihat keindahan grafis demo kecil ini .

.