Apa itu Quick Sort?
Algoritma Quick Sort mengikuti pendekatan Divide and Conquer. Ini membagi elemen menjadi bagian-bagian yang lebih kecil berdasarkan beberapa kondisi dan melakukan operasi pengurutan pada bagian-bagian yang lebih kecil.
Algoritme Pengurutan Cepat adalah salah satu algoritme yang paling banyak digunakan dan populer dalam bahasa pemrograman apa pun. Namun, jika Anda seorang pengembang JavaScript, Anda mungkin pernah mendengar tentang sort () yang sudah tersedia di JavaScript. Kemudian, Anda mungkin telah berpikir untuk apa algoritma Quick Sort ini. Untuk memahami ini, pertama-tama kita membutuhkan apa itu pengurutan dan apa pengurutan default di JavaScript.
Apa itu Sorting?
Menyortir tidak lain adalah mengatur elemen dalam urutan yang kita inginkan. Anda mungkin pernah menemukan ini di sekolah atau masa kuliah Anda. Seperti menyusun bilangan dari yang lebih kecil ke lebih besar (naik) atau dari lebih besar ke lebih kecil (turun) adalah apa yang kita lihat sampai sekarang dan disebut pengurutan.
Pengurutan default dalam JavaScript
Seperti yang disebutkan sebelumnya, JavaScript memiliki sort () . Mari kita ambil contoh dengan beberapa larik elemen seperti [5,3,7,6,2,9] dan ingin mengurutkan elemen larik ini dalam urutan menaik. Panggil saja sort () pada array item dan itu akan mengurutkan elemen array dalam urutan menaik.
Kode:
var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]
Apa alasan memilih Pengurutan cepat daripada pengurutan default () di JavaScript
Meskipun sort () memberikan hasil yang kita inginkan, masalahnya terletak pada cara mengurutkan elemen array. Pengurutan default () di JavaScript menggunakan pengurutan penyisipan oleh V8 Engine dari Chrome dan Pengurutan gabungan oleh Mozilla Firefox dan Safari .
Namun, hal lain ini tidak cocok jika Anda perlu mengurutkan elemen dalam jumlah besar. Jadi, solusinya adalah dengan menggunakan Quick sort untuk dataset besar.
Jadi, untuk memahami sepenuhnya, Anda perlu mengetahui cara kerja Quick sort dan beri tahu kami secara mendetail sekarang.
Apa itu Quick Sort?
Pengurutan cepat mengikuti algoritma Divide and Conquer . Ini membagi elemen menjadi bagian-bagian yang lebih kecil berdasarkan beberapa kondisi dan melakukan operasi pengurutan pada bagian-bagian yang lebih kecil. Karenanya, ini berfungsi dengan baik untuk kumpulan data besar. Jadi, berikut adalah langkah-langkah cara kerja Quick sort dengan kata-kata sederhana.
- Pertama pilih elemen yang akan disebut sebagai elemen pivot .
- Selanjutnya, bandingkan semua elemen larik dengan elemen pivot yang dipilih dan susun sedemikian rupa sehingga, elemen yang lebih kecil dari elemen pivot di sebelah kiri dan lebih besar dari pivot di sebelah kanan.
- Terakhir, lakukan operasi yang sama pada elemen sisi kiri dan kanan ke elemen pivot.
Jadi, itulah garis besar dasar dari Quick sort. Berikut adalah langkah-langkah yang perlu diikuti satu per satu untuk melakukan pengurutan cepat.
Bagaimana QuickSort Bekerja
- Pertama temukan elemen "pivot" dalam larik.
- Mulai penunjuk kiri di elemen pertama larik.
- Mulai penunjuk kanan di elemen terakhir dari array.
- Bandingkan elemen yang menunjuk dengan penunjuk kiri dan jika lebih kecil dari elemen pivot, pindahkan penunjuk kiri ke kanan (tambahkan 1 ke indeks kiri). Lanjutkan ini sampai elemen sisi kiri lebih besar dari atau sama dengan elemen pivot.
- Bandingkan elemen yang menunjuk dengan penunjuk kanan dan jika lebih besar dari elemen pivot, maka pindahkan penunjuk kanan ke kiri (kurangi 1 ke indeks kanan). Lanjutkan ini sampai elemen sisi kanan kurang dari atau sama dengan elemen pivot.
- Periksa apakah penunjuk kiri kurang dari atau sama dengan penunjuk kanan, kemudian lihat elemen di lokasi penunjuk ini.
- Tingkatkan penunjuk kiri dan kurangi penunjuk kanan.
- Jika indeks penunjuk kiri masih kurang dari indeks penunjuk kanan, ulangi proses tersebut; lain mengembalikan indeks penunjuk kiri.
Jadi, mari kita lihat langkah-langkah ini dengan sebuah contoh. Mari kita anggap array elemen yang perlu kita sortir adalah [5,3,7,6,2,9].
Tentukan elemen Pivot
Namun sebelum melanjutkan dengan Pengurutan cepat, memilih elemen pivot memainkan peran utama. Jika Anda memilih elemen pertama sebagai elemen pivot, maka ini memberikan kinerja terburuk dalam larik yang diurutkan. Jadi, selalu disarankan untuk memilih elemen tengah (panjang array dibagi 2) sebagai elemen pivot dan kami melakukan hal yang sama.
Berikut adalah langkah-langkah untuk melakukan Pengurutan cepat yang ditunjukkan dengan contoh [5,3,7,6,2,9].
LANGKAH 1: Tentukan poros sebagai elemen tengah. Jadi, 7 adalah elemen pivot.
LANGKAH 2: Mulai penunjuk kiri dan kanan sebagai elemen pertama dan terakhir dari larik. Jadi, penunjuk kiri menunjuk ke 5 pada indeks 0 dan penunjuk kanan menunjuk ke 9 pada indeks 5.
LANGKAH 3: Bandingkan elemen di penunjuk kiri dengan elemen pivot. Karena, 5 <6 menggeser penunjuk kiri ke kanan ke indeks 1.
LANGKAH 4: Sekarang, masih 3 <6 jadi geser penunjuk kiri ke satu indeks lagi ke kanan. Jadi sekarang 7> 6 berhenti menaikkan penunjuk kiri dan sekarang penunjuk kiri berada di indeks 2.
LANGKAH 5: Sekarang, bandingkan nilai di penunjuk kanan dengan elemen pivot. Karena 9> 6 pindahkan penunjuk kanan ke kiri. Sekarang sebagai 2 <6 berhenti menggerakkan penunjuk kanan.
LANGKAH 6: Tukar kedua nilai yang ada di penunjuk kiri dan kanan satu sama lain.
LANGKAH 7: Pindahkan kedua penunjuk satu langkah lagi.
LANGKAH 8: Karena 6 = 6, pindahkan penunjuk ke satu langkah lagi dan berhenti saat penunjuk kiri melintasi penunjuk kanan dan mengembalikan indeks penunjuk kiri.
Jadi, di sini berdasarkan pendekatan di atas, kita perlu menulis kode untuk menukar elemen dan mempartisi array seperti yang disebutkan pada langkah-langkah di atas.
Kode untuk menukar dua angka di JavaScript:
function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}
Kode untuk melakukan partisi seperti yang disebutkan dalam langkah-langkah di atas:
function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}
Lakukan operasi rekursif
Setelah Anda melakukan langkah-langkah di atas, indeks penunjuk kiri akan dikembalikan dan kita perlu menggunakannya untuk membagi array dan melakukan penyortiran Cepat pada bagian itu. Oleh karena itu, ini disebut algoritma Divide and Conquer.
Jadi, Quick sort dilakukan hingga semua elemen pada array kiri dan kanan diurutkan.
Catatan: Pengurutan cepat dilakukan pada larik yang sama dan tidak ada larik baru yang dibuat dalam prosesnya.
Jadi, kita perlu memanggil partisi ini () yang dijelaskan di atas dan berdasarkan itu kita membagi array menjadi beberapa bagian. Inilah kode yang Anda gunakan,
function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);
Lengkapi kode sortir cepat:
var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]
CATATAN: Pengurutan cepat berjalan dengan Kompleksitas Waktu O (nlogn).