Algoritma QuickSort di JavaNaskah
Apa itu Penyortiran Cepat?
Sortir Cepat algoritma mengikuti pendekatan Divide and Conquer. Ini membagi elemen menjadi bagian-bagian yang lebih kecil berdasarkan beberapa kondisi dan melakukan operasi pengurutan pada bagian-bagian kecil yang terbagi tersebut.
Algoritma Quick Sort merupakan salah satu algoritma yang paling banyak digunakan dan populer dalam bahasa pemrograman apa pun. Namun, jika Anda seorang JavaPengembang skrip, maka Anda mungkin pernah mendengarnya menyortir() yang sudah tersedia di JavaScript. Lalu, Anda mungkin berpikir apa perlunya algoritma Quick Sort ini. Untuk memahami ini, pertama-tama kita perlu tahu apa itu sorting dan apa sorting default di JavaNaskah.
Apa itu Penyortiran?
Sorting tidak lain adalah menyusun elemen-elemen sesuai urutan yang kita inginkan. Anda mungkin pernah menemukan ini di masa sekolah atau kuliah Anda. Seperti mengurutkan bilangan dari kecil ke besar (ascending) atau dari besar ke kecil (descending) itulah yang kita lihat selama ini dan disebut pengurutan.
Penyortiran default JavaNaskah
Seperti yang disebutkan sebelumnya, JavaNaskah sudah ada menyortir(). Mari kita ambil contoh dengan beberapa elemen array seperti [5,3,7,6,2,9] dan ingin mengurutkan elemen array ini dalam urutan menaik. Telepon saja menyortir() pada array item dan 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 untuk memilih Penyortiran cepat daripada penyortiran default() di JavaNaskah
Meskipun sort() memberikan hasil yang kita inginkan, masalahnya terletak pada cara mengurutkan elemen array. Sortir default() di JavaPenggunaan skrip jenis penyisipan by Mesin V8 Chrome dan Gabungkan semacam by Mozilla Firefox dan Safari.
Namun, cara lain ini tidak cocok jika Anda perlu mengurutkan elemen dalam jumlah besar. Jadi, solusinya adalah dengan menggunakan Quick sort untuk dataset berukuran besar.
Jadi, untuk memahami sepenuhnya, Anda perlu mengetahui cara kerja Penyortiran cepat dan mari kita lihat secara detail sekarang.
Apa itu Penyortiran cepat?
Penyortiran cepat menyusul Membagi dan menaklukkan algoritma. Ini membagi elemen menjadi bagian-bagian yang lebih kecil berdasarkan beberapa kondisi dan melakukan operasi pengurutan pada bagian-bagian kecil yang dibagi tersebut. Oleh karena itu, ini berfungsi dengan baik untuk kumpulan data besar. Nah, berikut langkah-langkah cara kerja Quick sort dengan kata-kata sederhana.
- Pertama pilih elemen yang akan disebut sebagai poros elemen.
- Selanjutnya, bandingkan semua elemen array dengan elemen pivot yang dipilih dan atur sedemikian rupa sehingga, elemen yang lebih kecil dari elemen pivot berada di sebelah kirinya dan lebih besar dari pivot berada di sebelah kanannya.
- Terakhir, lakukan operasi yang sama pada elemen sisi kiri dan kanan elemen pivot.
Nah, itulah garis besar dasar dari Quick sort. Berikut langkah-langkah yang perlu diikuti satu per satu untuk melakukan Quick sort.
Bagaimana QuickSort Bekerja
- Pertama temukan "poros" elemen dalam array.
- Mulai penunjuk kiri pada elemen pertama array.
- Mulai penunjuk kanan pada elemen terakhir array.
- Bandingkan elemen penunjuk dengan penunjuk kiri dan jika lebih kecil dari elemen pivot, pindahkan penunjuk kiri ke kanan (tambahkan 1 pada indeks kiri). Lanjutkan ini sampai elemen sisi kiri lebih besar atau sama dengan elemen pivot.
- Bandingkan elemen penunjuk 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 lebih kecil atau sama dengan penunjuk kanan, lalu tukar elemen di lokasi penunjuk tersebut.
- Menambah penunjuk kiri dan mengurangi penunjuk kanan.
- Jika indeks penunjuk kiri masih lebih kecil dari indeks penunjuk kanan, ulangi prosesnya; jika tidak, kembalikan indeks penunjuk kiri.
Jadi, mari kita lihat langkah-langkah ini dengan sebuah contoh. Mari kita perhatikan array elemen yang perlu kita urutkan 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 elemen tersebut akan memberikan performa terburuk dalam array yang diurutkan. Jadi, selalu disarankan untuk memilih elemen tengah (panjang array dibagi 2) sebagai elemen pivot dan kita melakukan hal yang sama.
Berikut langkah-langkah melakukan Quick sort yang ditunjukkan dengan contoh [5,3,7,6,2,9].
LANGKAH 1: Tentukan pivot sebagai elemen tengah. Jadi, 7 adalah elemen poros.
LANGKAH 2: Mulai penunjuk kiri dan kanan masing-masing sebagai elemen pertama dan terakhir dari array. 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 untuk mengindeks 1.
LANGKAH 4: Sekarang, masih 3 <6 jadi geser penunjuk kiri ke satu indeks lagi ke kanan. Jadi sekarang 7 > 6 berhenti menambah penunjuk kiri dan sekarang penunjuk kiri berada di indeks 2.
LANGKAH 5: Sekarang, bandingkan nilai pada penunjuk kanan dengan elemen pivot. Karena 9 > 6 gerakkan penunjuk kanan ke kiri. Sekarang 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 kembalikan indeks penunjuk kiri.
Jadi, berdasarkan pendekatan di atas, kita perlu menulis kode untuk menukar elemen dan mempartisi array seperti yang disebutkan pada langkah di atas.
Kode untuk menukar dua angka di JavaNaskah
function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; }
Kode untuk melakukan partisi seperti yang disebutkan pada langkah di atas
function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //swap two elements i++; 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 pengurutan cepat pada bagian itu. Oleh karena itu, ini disebut algoritma Divide and Conquer.
Jadi, pengurutan cepat dilakukan hingga semua elemen pada larik kiri dan larik kanan terurut.
Catatan: Pengurutan cepat dilakukan pada larik yang sama dan tidak ada larik baru yang dibuat dalam proses tersebut.
Jadi, kita perlu menyebutnya partisi () dijelaskan di atas dan berdasarkan itu kami membaginya susunan menjadi beberapa bagian. Jadi inilah kode tempat Anda menggunakannya,
function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var result = quickSort(items, 0, items.length - 1);
Lengkapi kode pengurutan 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 element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //sawpping two elements i++; j--; } } return i; } function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var sortedArray = quickSort(items, 0, items.length - 1); console.log(sortedArray); //prints [2,3,5,6,7,9]
CATATAN: Pengurutan cepat berjalan dengan Kompleksitas Waktu HAI(tidak masuk).