Penjelasan lengkap quick sort C++
Baca juga: Penjelasan lengkap merge sort C++
Quick sort bekerja dengan menukarkan bagian yang lebih besar dari pivot di letakkan disebelah kanan pivot sementara bagian yang lebih kecil dari pivot diletakkan disebelah kiri pivot.
Pivot dapat berada dimanapun. Pivot dapat berada diawal, diakhir, ditengah atau diambil secara random. Penentuan pivot tergantung dari programmer yang membuat algoritma tersebut berjalan.
Quick sort memiliki kompleksitas O(n log n). log disini menggunakan basis 2, Dibandingkan dengan insertion sort, selection sort, dan bubble sort; algoritma quick sort harusnya memiliki kecepatan yang lebih cepat. Ini akan terasa jika anda mengurutkan bilangan yang sangat banyak.
Baca juga: Pengertian algoritma komputer
Bagaimana quick sort bekerja. Quick sort bekerja seperti deskripsi dibawah ini.
- Ambil sembarang angka sebagai pivot.
- Gunakan variable i adalah awal dari array dikurangi 1, dan j adalah awal dari array.
- Bandingkan j dengan pivot,
- Apabila j lebih kecil sama dengan dari pivot, tambahkan i dan tukar array[i] dan array[j].
- Bagi angka diantara pivot menjadi dua bagian,
- ulangi langkah 2 sampai terurut.
Worst case quick sort
Semua algoritma memiliki worst case, begitu juga dengan quick sort. Algoritma ini memiliki worst case ketika proses partisi selalu mengambil bilangan terbesar atau terkecil sebagai pivot. Apabila pivot diambil diakhir array quick sort akan mengalami worst case saat mengurutkan bilangan yang sudah terurut.
Contoh sorting quick sort
Disini kita menggunakan array index terakhir sebagai pivot
arr[5] = {10, 30, 50, 20, 40};
awal = 0, akhir = 4, pivot = arr[akhir] = 40;
Menginisialisasi i = awal - 1 = -1;
Melakukan perulangan dari j = low sampai dengan high - 1
untuk j = 0 : arr[j] <= pivot, lakukan i++ dan tukar array[i] dengan array[j]
i = 0
Karena i dan j sama, maka pertukaran akan menghasilkan nilai yang sama.
arr[] = {10, 30, 50, 20, 40}
untuk j = 1 : arr[j] <= pivot, lakukan i++ dan tukar array[i] dengan array [j]
i = 1
Karena i dan j sama, maka pertukaran akan menghasilkan nilai yang sama.
arr[] = {10, 30, 50, 20, 40}
untuk j = 2 : arr[j] <= pivot, karena tidak dipenuhi lanjutkan ke perulangan selanjutnya.
i = 1
arr[] = {10, 30, 50, 20, 40}
untuk j = 3 : arr[j] <= pivot, lakukan i++ dan tukar array[i] dengan array [j]
i = 2
arr[] = {10, 30, 20, 50, 40}
Setelah ini kita selesai melakukan perulangan selanjutnya kita menukar letak pivot. Pivot ditukar dengan arr[i + 1} dan arr[akhir] (atau pivot).
arr[5] = {10, 20, 30, 40, 50};
Sekarang pivot telah diletakkan pada tempat yang semestinya. Jika belum terurut lakukan hal tersebut di bagian kiri pivot dan bagian kanan pivot.
Source code quick sort
Sebelum melihat kode program, saya sarankan untuk mencoba membuatnya terlebih dahulu. Jika sudah silakan lihat kode program dibawah ini.
>
Itu tadi adalah penjelasan mengenai algoritma quick sort. Algoritma quick sort sebenarnya dapat berbeda-beda. Namun ciri dari quick sort adalah peletakkan bilangan yang lebih kecil disebelah kiri pivot dan bilangan yang lebih besar disebelah kanan pivot.
Apabila ada yang ditanyakan tinggalkan di kolom komentar.
Berkomentarlah secara bijak.
EmoticonEmoticon