Kedua-dua teknik penyortiran, semacam cepat dan gabungan gabungan dibina di atas kaedah membahagikan dan menaklukkan di mana set elemen dipisahkan dan kemudian digabungkan selepas penyusunan semula. Semoga cepat memerlukan lebih banyak perbandingan daripada gabungan jenis untuk menyusun satu set besar elemen.
Carta Perbandingan
| Asas untuk perbandingan | Semak cepat | Gabungkan jenis |
|---|---|---|
| Pembahagian elemen dalam tatasusunan | Pemisahan senarai elemen tidak semestinya dibahagikan kepada separuh. | Array sentiasa terbahagi kepada separuh (n / 2). |
| Kerumitan kes terburuk | O (n2) | O (n log n) |
| Bekerja dengan baik | Arahan yang lebih kecil | Beroperasi dengan baik dalam pelbagai jenis. |
| Kelajuan | Lebih cepat daripada algoritma sorting lain untuk set data kecil. | Kelajuan yang konsisten dalam semua jenis set data. |
| Keperluan ruang storan tambahan | Kurang | Lebih banyak |
| Kecekapan | Tidak cekap untuk tatasusunan yang lebih besar. | Lebih cekap. |
| Kaedah penyisihan | Dalaman | Luar |
Takrif Pantas Pantas
Urut cepat adalah algoritma pemisahan yang digunakan secara meluas karena cepat untuk array pendek. Set elemen dibahagikan kepada beberapa bahagian sehingga tidak mungkin untuk membahagikannya lagi. Jenis pantas juga dikenali sebagai jenis pertukaran partisi . Ia menggunakan elemen utama (dikenali sebagai pivot) untuk memisahkan unsur-unsur. Satu partition mengandungi unsur-unsur yang lebih kecil daripada elemen utama. Satu lagi partition mengandungi unsur-unsur yang lebih besar daripada elemen utama. Unsur-unsur disusun secara rekursif.
Katakan A adalah array A [1], A [2], A [3], ...... .., A [n] nombor n yang perlu disusun. Algoritma jenis cepat terdiri daripada langkah-langkah berikut.
- Unsur pertama atau elemen rawak yang dipilih sebagai kunci, anggap kunci = A (1).
- Penunjuk "rendah" diletakkan pada penunjuk kedua dan "atas" diletakkan pada elemen terakhir array, iaitu rendah = 2 dan up = n;
- Secara konsisten, kenaikan penunjuk "rendah" dengan satu kedudukan sehingga (kekunci A [rendah]>).
- Sentiasa, menurunkan penunjuk "naik" dengan satu kedudukan sehingga (A [up] <= key).
- Jika naik lebih tinggi daripada persimpangan rendah A [rendah] dengan A [naik].
- Ulangi langkah 3, 4, dan 5 hingga keadaan di langkah 5 gagal (yaitu naik <= rendah) kemudian bertukar A [atas] dengan kunci.
- Sekiranya unsur-unsur kiri kekunci adalah lebih kecil daripada kekunci dan elemen kanan kekunci adalah lebih besar daripada kekunci maka array dibahagikan kepada dua sub-array.
- Prosedur di atas berulang kali diterapkan pada subaren sehingga keseluruhan array disusun.
Kelebihan dan kekurangan
Ia mempunyai perilaku kes purata yang baik. Kerumitan masa berjalan cepat adalah baik yang lebih cepat daripada algoritma seperti jenis gelembung, pemasukan jenis dan pemilihan jenis. Walau bagaimanapun, ia adalah kompleks dan sangat rekursif, itulah sebabnya ia tidak sesuai untuk tatasusunan yang besar.
Definisi Gabungan Susun
Merge sort adalah algoritma luaran yang juga berdasarkan strategi membahagikan dan menaklukkan. Unsur-unsur dibahagikan kepada sub-arrays (n / 2) lagi dan lagi sehingga hanya satu elemen yang tersisa, yang secara signifikan dapat menurunkan waktu penyortiran. Ia menggunakan storan tambahan untuk menyimpan pelbagai bantu. Merge sort menggunakan tiga array di mana dua digunakan untuk menyimpan setiap separuh, dan yang ketiga digunakan untuk menyimpan senarai disusun akhir. Setiap array kemudian diisih secara rekursif. Akhirnya, subarrays digabungkan untuk menjadikannya n unsur saiz array. Senarai ini selalu dibahagikan kepada separuh (n / 2) yang tidak sama dengan jenis yang cepat.
Let A menjadi array n bilangan unsur yang akan disusun A [1], A [2], ........., A [n]. Susunan gabungan berikut langkah-langkah yang diberikan.
- Berpisah dengan array A ke dalam n / 2 sub-array yang disusun mengikut 2, yang bermaksud bahawa unsur-unsur dalam (A [1], A [2]), (A [3], A [4] k], A [k + 1]), (A [n-1], A [n]) sub-array mesti dalam urutan yang disusun.
- Gabungkan setiap pasang pasangan untuk mendapatkan senarai subarrays yang disusun saiz 4; unsur-unsur dalam subarrat juga dalam urutan yang disusun, (A [1], A [2], A [3], A [4]), ......, (A [k-1], A [k], A [k + 1], A [k + 2]), ......., (A [n-3], A [n-2], A [n-1], A [n]).
- Langkah 2 berulang kali dilakukan sehingga hanya terdapat satu susunan array berukuran n.
Kelebihan dan kekurangan
Algoritma jenis gabungan berfungsi dengan cara yang sama dan tepat tanpa mengira bilangan elemen yang terlibat dalam penyortiran. Ia berfungsi dengan baik walaupun dengan set data yang besar. Walau bagaimanapun, ia menggunakan sebahagian besar ingatan.
Perbezaan Kekunci Antara Susun Pantas dan Gabungkan Susun
- Dalam jenis gabungan, array mesti dipisahkan kepada hanya dua bahagian (iaitu n / 2). Sebaliknya, dengan pantas, tidak ada paksaan membahagikan senarai ke elemen yang sama.
- Kerumitan kes terburuk yang cepat adalah O (n2) kerana ia memerlukan lebih banyak perbandingan dalam keadaan yang paling teruk. Sebaliknya, gabungan gabungan mempunyai kes terburuk yang sama dan kerumitan kes purata, iaitu O (n log n).
- Merge sort dapat beroperasi dengan baik pada semua jenis data yang ditetapkan apakah itu besar atau kecil. Sebaliknya, jenis pantas tidak dapat berfungsi dengan baik dengan dataset yang besar.
- Semacam pantas lebih cepat daripada menyusun semacam dalam beberapa kes seperti untuk set data kecil.
- Merge sort memerlukan ruang memori tambahan untuk menyimpan array tambahan. Sebaliknya, jenis cepat tidak memerlukan banyak ruang untuk penyimpanan tambahan.
- Merge sort lebih berkesan daripada semacam pantas.
- Susunan cepat ialah kaedah menyusun dalaman di mana data yang perlu disusun disesuaikan pada satu masa dalam ingatan utama. Sebaliknya, jenis penggabungan adalah kaedah penyisihan luaran di mana data yang perlu disusun tidak dapat ditampung dalam ingatan pada masa yang sama dan ada yang perlu disimpan dalam ingatan tambahan.
Kesimpulannya
Semoga cepat adalah kes yang lebih pantas tetapi tidak cekap dalam beberapa situasi dan juga melakukan banyak perbandingan dibandingkan dengan menyusun semacam. Walaupun jenis gabungan memerlukan kurang perbandingan, ia memerlukan ruang memori tambahan sebanyak 0 (n) untuk menyimpan array tambahan sementara keperluan semacam pantas ruang O (log n).
