Kedua teknik pengurutan, pengurutan cepat dan pengurutan gabungan dibangun di atas metode membagi dan menaklukkan di mana set elemen dipisahkan dan kemudian digabungkan setelah penataan ulang. Pengurutan cepat biasanya membutuhkan lebih banyak perbandingan daripada pengurutan gabungan untuk mengurutkan kumpulan elemen yang besar.
Grafik perbandingan
| Dasar untuk perbandingan | Sortir cepat | Gabungkan semacam |
|---|---|---|
| Mempartisi elemen-elemen dalam array | Pemisahan daftar elemen tidak harus dibagi menjadi setengah. | Array selalu dibagi menjadi setengah (n / 2). |
| Kompleksitas kasus terburuk | O (n2) | O (n log n) |
| Bekerja dengan baik | Array yang lebih kecil | Beroperasi dengan baik dalam semua jenis array. |
| Kecepatan | Lebih cepat daripada algoritma pengurutan lainnya untuk kumpulan data kecil. | Kecepatan yang konsisten di semua jenis set data. |
| Persyaratan ruang penyimpanan tambahan | Kurang | Lebih |
| Efisiensi | Tidak efisien untuk array yang lebih besar. | Lebih efisien. |
| Metode penyortiran | Intern | Luar |
Definisi Sort Cepat
Pengurutan cepat sering digunakan algoritma pengurutan karena cepat untuk array pendek. Set elemen dibagi menjadi beberapa bagian berulang-ulang sampai tidak mungkin untuk membaginya lebih lanjut. Sortir cepat juga dikenal sebagai sortir pertukaran partisi . Itu menggunakan elemen kunci (dikenal sebagai pivot) untuk mempartisi elemen. Satu partisi berisi elemen-elemen yang lebih kecil dari elemen kunci. Partisi lain berisi elemen-elemen yang lebih besar dari elemen kunci. Elemen-elemen diurutkan secara rekursif.
Misalkan A adalah array A [1], A [2], A [3], …… .., A [n] dari nomor n yang harus disortir. Algoritma pengurutan cepat terdiri dari langkah-langkah berikut.
- Elemen pertama atau elemen acak apa pun yang dipilih sebagai kunci, asumsikan kunci = A (1).
- Pointer "rendah" ditempatkan pada pointer kedua dan "atas" diposisikan pada elemen terakhir dari array, yaitu low = 2 dan up = n;
- Secara konsisten, tambahkan pointer "rendah" dengan satu posisi hingga (tombol [rendah]>).
- Secara konstan, kurangi penunjuk "atas" dengan satu posisi hingga (tombol [atas] <=).
- Jika naik lebih besar dari pertukaran rendah A [rendah] dengan A [atas].
- Ulangi langkah 3, 4, dan 5 hingga kondisi pada langkah 5 gagal (yaitu naik <= rendah) kemudian gantilah A [naik] dengan kunci.
- Jika elemen kiri kunci lebih kecil dari kunci dan elemen kanan kunci lebih besar dari kunci maka array dipartisi menjadi dua sub-array.
- Prosedur di atas berulang kali diterapkan pada subarrays hingga seluruh array diurutkan.
Keuntungan dan kerugian
Ia memiliki perilaku kasus rata-rata yang baik. Kompleksitas waktu berjalan dari jenis cepat adalah baik karena itu lebih cepat daripada algoritma seperti jenis gelembung, jenis penyisipan dan jenis pilihan. Namun, ini kompleks dan sangat rekursif, itu sebabnya tidak cocok untuk array besar.
Definisi Urutkan Gabung
Merge sort adalah algoritma eksternal yang juga didasarkan pada strategi divide and conquer. Elemen-elemen dibagi menjadi sub-array (n / 2) berulang-ulang sampai hanya satu elemen yang tersisa, yang secara signifikan mengurangi waktu penyortiran. Ini menggunakan penyimpanan tambahan untuk menyimpan array tambahan. Sortir gabungan menggunakan tiga array di mana dua digunakan untuk menyimpan masing-masing setengah, dan yang ketiga digunakan untuk menyimpan daftar akhir yang diurutkan. Setiap array kemudian disortir secara rekursif. Akhirnya, subarrays digabung untuk membuatnya menjadi ukuran elemen array. Daftar selalu dibagi menjadi hanya setengah (n / 2) berbeda untuk pengurutan cepat.
Misalkan A adalah array dari n jumlah elemen yang akan diurutkan A [1], A [2], ………, A [n]. Sortir gabungan mengikuti langkah-langkah yang diberikan.
- Membagi array A menjadi sekitar n / 2 diurutkan sub-array oleh 2, yang berarti bahwa elemen dalam (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) sub-array harus berurutan.
- Gabungkan masing-masing pasangan untuk mendapatkan daftar subarrays yang diurutkan berukuran 4; elemen-elemen dalam sub-susunan juga dalam urutan, (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 dilakukan berulang kali hingga hanya ada satu array ukuran diurutkan n.
Keuntungan dan kerugian
Algoritme penggabungan melakukan dalam cara yang persis sama dan tepat terlepas dari jumlah elemen yang terlibat dalam penyortiran. Ini berfungsi dengan baik bahkan dengan set data yang besar. Namun, ia menghabiskan sebagian besar memori.
Perbedaan Kunci Antara Sortir Cepat dan Sortir Penggabungan
- Dalam semacam gabungan, array harus dibagi menjadi hanya dua bagian (yaitu n / 2). Sebagai lawan, dalam penyortiran cepat, tidak ada keharusan membagi daftar menjadi elemen yang sama.
- Kompleksitas terburuk dari penyortiran cepat adalah O (n2) karena dibutuhkan banyak perbandingan dalam kondisi terburuk. Sebaliknya, jenis gabungan memiliki kasus terburuk dan kompleksitas kasus rata-rata yang sama, yaitu O (n log n).
- Jenis gabungan dapat beroperasi dengan baik pada semua jenis kumpulan data apakah itu besar atau kecil. Sebaliknya, pengurutan cepat tidak dapat bekerja dengan baik dengan kumpulan data besar.
- Pengurutan cepat lebih cepat daripada menggabungkan pengurutan dalam beberapa kasus seperti untuk set data kecil.
- Gabung semacam memerlukan ruang memori tambahan untuk menyimpan array tambahan. Di sisi lain, penyortiran cepat tidak memerlukan banyak ruang untuk penyimpanan ekstra.
- Jenis penggabungan lebih efisien daripada jenis cepat.
- Penyortiran cepat adalah metode penyortiran internal di mana data yang akan disortir disesuaikan pada suatu waktu di memori utama. Sebaliknya, jenis gabungan adalah metode penyortiran eksternal di mana data yang akan disortir tidak dapat ditampung dalam memori pada saat yang sama dan beberapa harus disimpan dalam memori tambahan.
Kesimpulan
Penyortiran cepat adalah kasus yang lebih cepat tetapi tidak efisien dalam beberapa situasi dan juga melakukan banyak perbandingan dibandingkan dengan penggabungan. Meskipun penggabungan penggabungan membutuhkan sedikit perbandingan, ini membutuhkan ruang memori tambahan 0 (n) untuk menyimpan array tambahan sementara penyortiran cepat membutuhkan ruang O (log n).
