Cepat menyortir sebagai metode pemrograman

Pada tahun 1960, K. A. Hoare mengembangkan metode penyortiran informasi yang cepat, yang menjadi paling terkenal. Hari ini banyak digunakan dalam pemrograman, karena memiliki banyak sifat positif: dapat digunakan untuk kasus umum, memerlukan sedikit peningkatan memori tambahan, kompatibel dengan berbagai jenis daftar dan mudah dilakukan. Tapi ada juga kelemahan yang bisa disortir dengan cepat: bila digunakan dalam pekerjaan memungkinkan banyak kesalahan dan agak tidak stabil.

Namun, ini adalah versi yang paling banyak dipelajari. Setelah munculnya perhitungan pertama Hoar, banyak yang terlibat dalam studinya yang padat. Dasar besar diciptakan pada pertanyaan teoritis untuk menemukan waktu yang digunakan untuk bekerja, yang didukung oleh data empiris. Ada usulan nyata untuk memperbaiki algoritma utama dan meningkatkan kecepatan kerja.

Pemilahan cepat sangat umum, bisa ditemukan dimana-mana. Hal ini didasarkan pada metode TList.Sort, yang ada di semua versi (kecuali untuk 1) Delphi, fungsi perpustakaan dari waktu yang dihabiskan untuk dieksekusi, qsort di C ++.

Prinsip dasar kerja dapat diformulasikan sebagai "membagi dan menaklukkan". Ada rincian daftar menjadi dua kelompok dan pemilahan dilakukan untuk masing-masing bagian dengan sendirinya. Oleh karena itu, perhatian lebih harus diberikan pada proses pemisahan, selama hal-hal berikut terjadi: elemen dasar ditentukan dan seluruh daftar sudah bergeser relatif terhadapnya. Sekelompok kandidat terbentuk di sebelah kiri, nilai yang lebih kecil, semua yang lain dipindahkan ke kanan. Ternyata elemen utama dalam daftar diurutkan terletak di tempat yang seharusnya. Langkah selanjutnya adalah memanggil fungsi sortir rekursif untuk kedua sisi elemen relatif terhadap basis. Proses kerja berakhir hanya bila daftar hanya berisi satu elemen, yaitu, prosesnya akan diurutkan. Jadi, untuk menguasai fungsi pemrograman seperti penyortiran cepat, perlu diketahui pengoperasian algoritma tingkat rendah: a) pemilihan elemen dasar; B) permutasi paling efektif dari daftar untuk mendapatkan dua perangkat dengan nilai lebih kecil dan lebih besar.

Kita akan berkenalan dengan prinsip-prinsip yang pertama. Saat memilih elemen dasar, idealnya yang tengah harus dipilih dari daftar. Kemudian, bila rusak, dibagi menjadi dua bagian yang sama. Hanya menghitung nilai rata - rata dalam daftar sangat sulit, sehingga pemilahan tercepat pun bisa melewati kalkulus ini di sampingnya. Tapi memilih elemen utama dengan nilai maksimal atau minimum juga bukan pilihan terbaik. Dalam kasus definisi seperti itu, salah satu daftar yang dibuat akan dijamin kosong, dan yang kedua diluap. Maka kesimpulan bahwa sebagai elemen dasar seseorang harus memilih yang mendekati rata-rata, tapi lebih jauh dari yang maksimal dan minimum.

Begitu Anda memutuskan pilihan, Anda bisa melanjutkan operasi algoritma partisi. Ini adalah siklus quick-sort internal yang disebut. Semuanya dibangun di atas dua indeks kerja cepat: yang pertama akan berlalu dari elemen ke kiri, yang kedua, sebaliknya, dari kanan ke kiri. Operasi eksekusi di sebelah kanan dimulai: indeks melewati daftar dan membandingkan semua nilai dengan yang utama. Siklus dianggap lengkap jika ada unsur kurang dari atau sama dengan basisnya. Artinya, nilai indeks dibandingkan dan menurun. Di sisi kiri, pekerjaan selesai bila nilai yang lebih besar atau sama ditemukan. Dan disini nilai perbandingannya bertambah.

Pada tahap algoritma partisi ini, yang berisi quick sort, dua situasi bisa muncul. Yang pertama adalah indeks di sebelah kiri kurang dari kanan. Ini menunjukkan adanya kesalahan, yaitu item yang telah ditentukan berada dalam urutan yang salah dalam daftar. Jalan keluarnya adalah mengubah tempat. Situasi kedua adalah ketika kedua kolom sama atau berpotongan. Hal ini mengindikasikan adanya pemisahan daftar yang berhasil, yaitu pekerjaan dapat dianggap selesai.