Apakah Susunan Pantas?
Algoritma Quick Sort mengikuti pendekatan Divide and Conquer. Ia membahagikan unsur-unsur menjadi bahagian-bahagian yang lebih kecil berdasarkan beberapa keadaan dan melakukan operasi semacam pada bahagian-bahagian yang lebih kecil yang dibahagikan.
Algoritma Quick Sort adalah salah satu algoritma yang paling banyak digunakan dan popular dalam mana-mana bahasa pengaturcaraan. Tetapi, jika anda seorang pengembang JavaScript, anda mungkin pernah mendengar tentang jenis () yang sudah tersedia dalam JavaScript. Kemudian, anda mungkin berfikir tentang keperluan algoritma Quick Sort ini. Untuk memahami perkara ini, pertama-tama kita memerlukan apa yang menyusun dan apakah penyortiran lalai dalam JavaScript.
Apakah Pengisihan?
Menyusun tidak lain adalah, menyusun elemen mengikut urutan yang kita mahukan. Anda mungkin pernah menemui perkara ini di sekolah atau kuliah anda pada hari-hari. Seperti menyusun angka dari lebih kecil ke lebih besar (menaik) atau dari lebih besar ke lebih kecil (menurun) adalah apa yang kita lihat hingga sekarang dan disebut menyusun.
Penyusunan lalai dalam JavaScript
Seperti yang disebutkan sebelumnya, JavaScript mempunyai semacam () . Mari kita ambil contoh dengan beberapa susunan elemen seperti [5,3,7,6,2,9] dan ingin menyusun elemen susunan ini mengikut tertib menaik. Cukup panggil urut () pada item item dan ia menyusun elemen susunan mengikut tertib menaik.
Kod:
var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]
Apa alasan untuk memilih Urut cepat daripada jenis lalai () dalam JavaScript
Walaupun sort () memberikan hasil yang kita inginkan, masalah terletak pada cara menyusun elemen array. Urut lalai () dalam JavaScript menggunakan penyisipan mengikut V8 Engine Chrome dan Penggabungan jenis oleh Mozilla Firefox dan Safari .
Tetapi, ini tidak sesuai jika anda perlu menyusun sebilangan besar elemen. Jadi, penyelesaiannya adalah dengan menggunakan Jenis cepat untuk set data yang besar.
Oleh itu, untuk memahami sepenuhnya, anda perlu mengetahui cara kerja Jenis cepat dan biarkan kami melihatnya secara terperinci sekarang.
Apakah jenis Pantas?
Urutan pantas mengikuti algoritma Divide and Conquer . Ia membahagikan unsur ke bahagian yang lebih kecil berdasarkan beberapa keadaan dan melakukan operasi penguraian pada bahagian yang lebih kecil yang dibahagi. Oleh itu, ia berfungsi dengan baik untuk set data yang besar. Jadi, berikut adalah langkah-langkah bagaimana pengurutan pantas berfungsi dengan kata mudah.
- Pertama pilih elemen yang akan dipanggil sebagai elemen pangsi .
- Seterusnya, bandingkan semua elemen larik dengan elemen pangsi yang dipilih dan susun sedemikian rupa sehingga elemen yang kurang daripada elemen pangsi berada di sebelah kiri dan lebih besar daripada pangsi di sebelah kanan.
- Akhirnya, lakukan operasi yang sama pada elemen sisi kiri dan kanan ke elemen pangsi.
Jadi, itu adalah garis besar asas jenis Cepat. Berikut adalah langkah-langkah yang perlu diikuti satu demi satu untuk melakukan Urutan pantas.
Bagaimana QuickSort Berfungsi
- Mula-mula cari elemen "pivot" dalam tatasusunan.
- Mulakan penunjuk kiri pada elemen pertama array.
- Mulakan penunjuk kanan pada elemen larik terakhir.
- Bandingkan elemen penunjuk dengan penunjuk kiri dan jika kurang dari elemen pangsi, kemudian gerakkan penunjuk kiri ke kanan (tambahkan 1 ke indeks kiri). Teruskan ini sehingga elemen sebelah kiri lebih besar daripada atau sama dengan elemen pangsi.
- Bandingkan elemen penunjuk dengan penunjuk kanan dan jika lebih besar daripada elemen pangsi, kemudian gerakkan penunjuk kanan ke kiri (tolak 1 ke indeks kanan). Teruskan ini sehingga elemen sebelah kanan kurang daripada atau sama dengan elemen pangsi.
- Periksa sama ada penunjuk kiri kurang dari atau sama dengan penunjuk kanan, kemudian lihat elemen di lokasi penunjuk ini.
- Tingkatkan penunjuk kiri dan tolak penunjuk kanan.
- Sekiranya indeks pointer kiri masih kurang daripada indeks pointer kanan, maka ulangi prosesnya; lain pulangkan indeks penunjuk kiri.
Oleh itu, mari kita lihat langkah-langkah ini dengan contoh. Mari kita pertimbangkan pelbagai elemen yang perlu kita susun adalah [5,3,7,6,2,9].
Tentukan elemen Pivot
Tetapi sebelum maju dengan Jenis cepat, memilih elemen pangsi memainkan peranan utama. Sekiranya anda memilih elemen pertama sebagai elemen pangsi, maka ia memberikan prestasi terburuk dalam susunan yang disusun. Oleh itu, selalu dianjurkan untuk memilih elemen tengah (panjang array dibahagi dengan 2) sebagai elemen pangsi dan kita melakukan perkara yang sama.
Berikut adalah langkah-langkah untuk melakukan Urutan pantas yang ditunjukkan dengan contoh [5,3,7,6,2,9].
LANGKAH 1: Tentukan pangsi sebagai elemen tengah. Jadi, 7 adalah elemen pangsi.
LANGKAH 2: Mulakan penunjuk kiri dan kanan sebagai elemen susunan pertama dan terakhir masing-masing. Jadi, penunjuk kiri menunjuk ke 5 pada indeks 0 dan penunjuk kanan menunjuk ke 9 pada indeks 5.
LANGKAH 3: Bandingkan elemen pada penunjuk kiri dengan elemen pangsi. Sejak, 5 <6 beralih penunjuk kiri ke kanan ke indeks 1.
LANGKAH 4: Sekarang, masih 3 <6 sehingga beralih penunjuk kiri ke satu lagi indeks ke kanan. Jadi sekarang 7> 6 berhenti meningkatkan penunjuk kiri dan sekarang penunjuk kiri berada di indeks 2.
LANGKAH 5: Sekarang, bandingkan nilai pada penunjuk kanan dengan elemen pangsi. Sejak 9> 6 gerakkan penunjuk kanan ke kiri. Sekarang sebagai 2 <6 berhenti bergerak penunjuk kanan.
LANGKAH 6: Tukar kedua-dua nilai yang terdapat pada titik kiri dan kanan antara satu sama lain.
LANGKAH 7: Gerakkan kedua-dua penunjuk satu langkah lagi.
LANGKAH 8: Sejak 6 = 6, gerakkan penunjuk ke satu langkah lagi dan berhenti ketika penunjuk kiri melintasi penunjuk kanan dan mengembalikan indeks penunjuk kiri.
Jadi, di sini berdasarkan pendekatan di atas, kita perlu menulis kod untuk menukar elemen dan memisahkan array seperti yang disebutkan di langkah-langkah di atas.
Kod untuk menukar dua nombor dalam JavaScript:
function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}
Kod untuk melakukan partisi seperti yang disebutkan di 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 kami perlu menggunakannya untuk membahagikan susunan dan melakukan Urutan Pantas pada bahagian tersebut. Oleh itu, ia dipanggil algoritma Divide and Conquer.
Jadi, Pengisihan pantas dilakukan sehingga semua elemen pada susunan kiri dan tatasusunan kanan disusun.
Catatan: Urutan cepat dilakukan pada susunan yang sama dan tidak ada tatasusunan baru yang dibuat dalam proses tersebut.
Oleh itu, kita perlu memanggil partisi ini () yang dijelaskan di atas dan berdasarkan bahawa kita membahagikan susunan menjadi beberapa bahagian. Jadi inilah kod di mana anda menggunakannya,
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);
Lengkapkan kod urutan Pantas:
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: Jenis cepat dijalankan dengan Kerumitan Masa O (nlogn).