Perbedaan yang menonjol antara quicksort dan merge sort adalah quicksort mengurutkan unsur dengan membandingkan setiap unsur dengan unsur yang disebut pivot sementara merge sort membagi array menjadi dua subarray berulang kali hingga tersisa satu unsur.
Sorting adalah cara menyusun data dalam urutan tertentu. Saat mengatur data, dimungkinkan untuk mempertimbangkan urutan numerik atau leksikografis. Penyortiran membantu untuk mencari dan mengakses unsur data lebih cepat dan lebih cepat. Ada berbagai algoritma pengurutan dan quicksort dan merge sort adalah dua di antaranya.
Topik bahasan kami tentang:
- Apa itu Quicksort? – Definisi, Fungsi 2. Apa itu Merge Sort – Definisi, Fungsi 3. Apa Perbedaan Antara Quicksort dan Merge Sort – Perbandingan Perbedaan Utama
Istilah Utama
Algoritma, Array, Merge Sort, Quicksort
Yang perlu anda ketahui tentang Quicksort?
Quicksort adalah algoritma internal yang menggunakan ‘teknik membagi dan menaklukkan’. Ini juga disebut semacam pertukaran partisi . Ini menggunakan unsur kunci yang disebut pivot untuk membandingkan dan mempartisi unsur dalam array. Item dengan nilai lebih rendah dari pivot pergi ke sisi kiri pivot sementara item dengan nilai lebih besar dari pivot pergi ke sisi kanan pivot. Bagian kiri disebut partisi kiri, dan bagian kanan disebut partisi kanan.
Gambar 1: Quicksort
Lihat contoh di bawah ini.
36 34 43 11 15 20 28 45 27 32
Pertimbangkan 32 sebagai pivot dan pertimbangkan 36 dan 27. Kondisi 36 < pivot, 27 > pivot salah. Maka dari itu, kita dapat menukar kedua nilai ini. Sekarang daftarnya adalah sebagai berikut.
27 34 43 11 15 20 28 45 36 32
Pertimbangkan nilai 34 dan 45. Saat mempertimbangkan 34 < pivot, kondisinya salah. Demikian pula, 45 > kondisi pivot benar. Sekarang, kita dapat berpindah dari 45 ke 28. Mari kita pertimbangkan 34 dan 28. 34 < pivot salah dan 28 > pivot salah. Maka dari itu, kita dapat menukar 34 dan 28.
27 28 43 11 15 20 34 45 36 32
Pertimbangkan 43 dan 20. 43 < pivot salah. 20 > pivot salah. Maka dari itu, kita dapat menukar kedua angka tersebut. Sekarang daftarnya adalah sebagai berikut.
27 28 20 11 15 43 34 45 36 32
Sekarang perhatikan 11 dan 15. 11 < pivot benar. Kita dapat mempertimbangkan 15. Ini kurang dari 32. Ini adalah titik yang tumpang tindih, dan kita dapat menempatkan 32 sebagai berikut.
27 28 20 11 15 32 43 34 45 36
Sekarang angka di sisi kiri pivot lebih kecil dari pivot, dan sisi kanan pivot lebih besar dari pivot. Kita dapat menerapkan quicksort ke partisi kiri dan kanan untuk mengurutkan seluruh daftar.
Yang perlu anda ketahui tentang Pengurutan Gabung?
Merge sort adalah algoritma eksternal yang menggunakan ‘teknik membagi dan menaklukkan’. Ini membagi array menjadi dua bagian. Ini mengurutkan setiap array dan menggabungkannya bersama untuk membentuk array yang diurutkan. Pengurutan gabungan memerlukan penyimpanan tambahan untuk mengurutkan larik bantu.
Perhatikan contoh berikut.
Gambar 2: Gabungkan Sortir
Kita dapat membagi array menjadi dua bagian. Sekarang ada dua array sebagai berikut.
38 27 43 3 9 82 10
Pertimbangkan 38 27 43 3. Kita dapat membaginya menjadi dua array lagi. Mereka adalah 38 27 dan 43 3. 38 27 membagi menjadi 38 dan 27 sedangkan 43 3 membagi menjadi 43 dan 3. Pengurutan 38 dan 27 menghasilkan 27 38. Pengurutan 43 3 menghasilkan 3 43. Sekarang dimungkinkan untuk menggabungkan 27 38 dan 3 43 Setelah mengurutkannya, kita mendapatkan array sebagai 3 27 38 43.
Demikian pula, pertimbangkan 9 82 10. Kita dapat membaginya menjadi dua array lagi. Mereka adalah 9 82 dan 10. 9 82 dibagi menjadi 9 dan 82. Apalagi ada nomor 10 di array lainnya. 9 dan 82 mengurutkan sebagai 9 82. Jadi, larik dan larik ini dengan nilai 10 menggabungkan dan menyediakan 9 10 dan 82.
Terakhir, 3 27 38 43 dan 9 10 82 digabungkan untuk menyediakan larik terurut.
Perbedaan Antara Quicksort dan Merge Sort
Definisi
Quicksort adalah algoritma pengurutan yang efisien, berfungsi sebagai metode sistematis untuk menempatkan unsur array secara berurutan. Sebaliknya, merge sort adalah algoritma pengurutan berbasis perbandingan yang efisien, tujuan umum. Jadi, inilah perbedaan mendasar antara quicksort dan merge sort.
Kegunaan
Di atas segalanya, fungsionalitas adalah Perbedaan yang menonjol antara quicksort dan merge sort. Quicksort mengurutkan unsur dengan membandingkan setiap unsur dengan pivot sementara merge sort membagi array menjadi dua subarray (n/2) berulang-ulang hingga tersisa satu unsur.
Aplikasi
Selain itu, meskipun quicksort cocok untuk array kecil, sortir gabungan berfungsi untuk semua jenis array.
Kecepatan
Perbedaan lain antara quicksort dan merge sort adalah quicksort bekerja lebih cepat untuk kumpulan data kecil sementara merge sort bekerja dalam kecepatan yang konsisten untuk semua kumpulan data.
Kebutuhan Ruang
Selain itu, kebutuhan ruang juga merupakan perbedaan penting antara quicksort dan merge sort. Quicksort membutuhkan ruang minimum dibandingkan dengan merge sort.
Efisiensi
Selanjutnya, quicksort tidak efisien untuk array besar, tetapi merge sort lebih efisien daripada quicksort. Maka dari itu, ini adalah perbedaan lain antara quicksort dan merge sort.
Kata terakhir
Singkatnya, Perbedaan yang menonjol antara quicksort dan merge sort adalah quicksort mengurutkan unsur dengan membandingkan setiap unsur dengan unsur yang disebut pivot, sedangkan merge sort membagi array menjadi dua subarray berulang kali hingga tersisa satu unsur.
Sumber bacaan:
- Algoritma Quicksort| Bagian 2, Pendidikan 4u, 15 Maret 2018, Tersedia di sini . 2. Contoh Sortir Penggabungan, Pendidikan 4u, 15 Maret 2018, Tersedia di sini .
Sumber gambar:
- “Quicksort-diagram” Oleh Znupi – Karya sendiri (Domain Publik) melalui Commons Wikimedia 2. “Gerge sort algoritma diagram” Oleh Vineet Kumar di Wikipedia bahasa Inggris – Ditransfer dari en.wikipedia ke Commons oleh Eric Bauman menggunakan CommonsHelper (Domain Publik) melalui Commons Wikimedia
