Algoritma QuickSort di JavaSkrip dengan Contoh

Apa itu Penyortiran Cepat?

Sortir Cepat adalah algoritma pengurutan perbandingan yang mengikuti Membagi dan menaklukkan Pendekatan ini memilih satu elemen sebagai pivot, membagi array menjadi bagian yang berisi nilai lebih kecil dari pivot dan bagian yang berisi nilai lebih besar, lalu menerapkan prosedur yang sama pada setiap bagian hingga seluruh array terurut.

Quick Sort adalah salah satu algoritma pengurutan yang paling banyak digunakan di setiap bahasa pemrograman. Jika Anda menulis JavaNaskahAnda mungkin sudah menggunakan fitur bawaan tersebut. menyortir() metode ini, jadi Anda mungkin bertanya-tanya mengapa implementasi Quick Sort terpisah layak dipelajari. Untuk menjawabnya, Anda perlu mengetahui terlebih dahulu apa arti pengurutan dan apa pengurutan default di JavaSkrip tersebut memang melakukannya.

Tiga properti mendefinisikan Quick Sort:

• Di tempat: Ini menata ulang yang asli susunan dan tidak mengalokasikan array kedua dengan ukuran yang sama.
• Rekursif: Setiap partisi menghasilkan dua rentang yang lebih kecil yang diurutkan dengan fungsi yang sama.
• Tidak stabil: Dua elemen dengan kunci yang sama mungkin akan berakhir dalam urutan relatif yang berbeda dari urutan awalnya.

Apa itu Penyortiran?

Mengurutkan berarti menyusun elemen-elemen dalam urutan yang telah ditentukan. Anda hampir pasti pernah menjumpai hal ini di sekolah: menyusun angka dari yang terkecil hingga yang terbesar adalah... naik urutan, dan menempatkannya dari yang terbesar hingga terkecil adalah turun Urutan. Pengurutan tidak terbatas pada angka. String dapat diurutkan secara alfabetis, tanggal secara kronologis, dan objek berdasarkan bidang apa pun yang Anda pilih, seperti harga atau skor.

Pengurutan itu penting karena data yang terurut memungkinkan operasi yang lebih cepat. Pencarian biner berjalan dalam waktu O(log n), tetapi hanya pada input yang terurut. Penghapusan duplikasi, kueri rentang, pemeringkatan, dan operasi penggabungan semuanya menjadi jauh lebih murah setelah data terurut, itulah sebabnya setiap bahasa pemrograman menyediakan setidaknya satu rutin pengurutan.

Pengurutan Default di JavaNaskah

Seperti yang disebutkan sebelumnya, JavaSkrip menyediakan menyortir()Ambil array kecil seperti [5,3,7,6,2,9] yang ingin Anda urutkan secara menaik. Panggil menyortir() pada array tampaknya melakukan hal yang persis sama.

Tangkapan layar di atas menunjukkan konsol browser yang mencetak array yang sudah diurutkan. Berikut kode yang sama:

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

Keluaran:

[ 2, 3, 5, 6, 7, 9 ]

Hasil itu benar, tetapi hanya secara kebetulan. Array.prototype.sort() mengubah setiap elemen menjadi string dan membandingkan string tersebut. kecuali jika Anda menyediakan fungsi pembanding. Setiap nilai dalam array ini adalah satu digit, jadi urutan string kebetulan cocok dengan urutan numerik. Ubah datanya dan ilusi itu akan hilang.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Keluaran:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

Algoritma apa yang digunakan oleh fungsi sort()?

Spesifikasi tersebut tidak menyebutkan algoritma tertentu, sehingga setiap mesin memilih algoritmanya sendiri. Semua mesin modern menggunakan algoritma berbasis penggabungan (merge-based algorithm):

• V8 (Chrome, Edge, Node.js) telah digunakan TimSort Sejak V8 7.0, dikirimkan di Chrome 70.
• Monyet laba-laba (Firefox) menggunakan menggabungkan semacam.
• JavaScriptCore (Safari) juga menggunakan menggabungkan semacam.

Sejak ES2019, bahasa tersebut menjamin bahwa sort() is stabil, yang meniadakan Quick Sort biasa di dalam mesin. Pengurutan berbasis penggabungan membutuhkan memori tambahan O(n), dan harus memanggil JavaSkrip pembanding untuk setiap perbandingan. Pengurutan Cepat numerik yang ditulis tangan membandingkan angka secara langsung dan mengurutkan di tempat, sehingga dapat unggul pada array numerik besar. Mengurutkan 1,000,000 bilangan bulat acak di Node.js 22 membutuhkan waktu sekitar 100 ms dengan Pengurutan Cepat di bawah ini dan kira-kira 210 ms dengan sort((a, b) => a - b).

Jadi, Quick Sort layak ditulis ketika Anda membutuhkan pengurutan di tempat, kontrol ketat atas memori, atau sekadar pemahaman yang solid tentang cara kerja pengurutan. Mari kita lihat mekanismenya secara detail.

Bagaimana Cara Kerja Pengurutan Cepat?

Quick Sort mengulang satu operasi inti, yang disebut partisi, pada rentang yang semakin kecil. Berikut langkah-langkahnya secara berurutan:

1. Cari poros elemen dalam array.
2. Arahkan kursor kiri ke elemen pertama dari rentang tersebut.
3. Arahkan kursor kanan ke elemen terakhir dari rentang tersebut.
4. Bandingkan elemen pada penunjuk kiri dengan titik tumpu. Jika nilainya kurang dari titik tumpu, geser penunjuk kiri satu langkah ke kanan. Lanjutkan hingga elemen kiri lebih besar atau sama dengan titik tumpu.
5. Bandingkan elemen pada penunjuk kanan dengan pivot. Jika lebih besar dari pivot, geser penunjuk kanan satu langkah ke kiri. Lanjutkan hingga elemen kanan kurang dari atau sama dengan pivot.
6. Jika penunjuk kiri masih kurang dari atau sama dengan penunjuk kanan, tukar kedua elemen tersebut.
7. Menambah penunjuk kiri dan mengurangi penunjuk kanan.
8. Jika indeks kiri masih kurang dari atau sama dengan indeks kanan, ulangi dari langkah 4. Jika tidak, kembalikan indeks penunjuk kiri.

Diagram di atas tracBerikut adalah pergerakan pointer pada sebuah array sampel. Setiap elemen yang lebih kecil dari pivot akan berada di sebelah kirinya dan setiap elemen yang lebih besar akan berada di sebelah kanannya, yang persis sesuai dengan indeks yang dikembalikan. Bagian di bawah ini akan menjelaskan array yang sama langkah demi langkah.

Cara Menentukan Elemen Pivot

Memilih pivot adalah satu-satunya keputusan yang membedakan Quick Sort yang cepat dari yang lambat. Jika Anda selalu memilih pertama elemen, sebuah array yang sudah diurutkan menghasilkan pemisahan terburuk: satu sisi kosong dan satu sisi dengan semua elemen yang tersisa. Itu mengubah algoritma menjadi O(n²). Mengambil tengah Elemen (panjang array dibagi dua) menghindari jebakan tersebut untuk input yang sudah diurutkan dan diurutkan terbalik, itulah sebabnya kode di bawah ini menggunakannya.

Strategi pivot umum:

• Elemen pertama atau terakhir: Paling mudah dikodekan, tetapi O(n²) pada data yang sudah diurutkan.
• Elemen tengah: sebuah nilai default yang baik yang menangani array yang sudah diurutkan dan diurutkan terbalik dalam waktu O(n log n).
• Elemen acak: membuat input skenario terburuk tidak mungkin dibuat sebelumnya.
• Median dari tiga: Mengambil nilai median dari nilai pertama, tengah, dan terakhir; pilihan standar dalam pustaka produksi.

Sekarang, mari kita bahas langkah-langkah Quick Sort pada array tersebut. [5,3,7,6,2,9].

LANGKAH 1: Pivot adalah elemen tengah. Dengan kiri = 0 dan kanan = 5, Math.floor((5 + 0) / 2) memberikan indeks 2, jadi nilai pivotnya adalah 7.

LANGKAH 2: Arahkan pointer dari ujung array. Pointer kiri berada di indeks 0 (nilai 5) dan penunjuk kanan berada di indeks 5 (nilai 9).

LANGKAH 3: Bandingkan nilai sebelah kiri dengan pivot. 5 < 7, jadi pindah ke kanan ke indeks 1. 3 < 7, jadi pindah ke kanan ke indeks 2. Nilai di sana adalah 7, yang tidak kurang dari pivot, jadi penunjuk sebelah kiri berhenti di indeks 2.

LANGKAH 4: Bandingkan nilai kanan dengan pivot. 9 > 7, jadi pindah ke kiri ke indeks 4. Nilai di sana adalah 2, yang tidak lebih besar dari pivot, jadi penunjuk kanan berhenti di indeks 4.

LANGKAH 5: Indeks kiri (2) kurang dari atau sama dengan indeks kanan (4), jadi tukar kedua nilai tersebut. Array menjadi [5,3,2,6,7,9].

LANGKAH 6: Geser kedua penunjuk satu langkah ke dalam. Penunjuk kiri sekarang berada di indeks 3 dan penunjuk kanan di indeks 3.

LANGKAH 7: Ulangi pemindaian. Nilai pada indeks 3 adalah 6, dan 6 < 7, sehingga penunjuk kiri bergerak ke indeks 4. Nilai pada indeks 3 tidak lebih besar dari pivot, sehingga penunjuk kanan tetap berada di indeks 3.

LANGKAH 8: Indeks kiri (4) sekarang lebih besar dari indeks kanan (3), sehingga loop berakhir dan fungsi kembali. 4Segala sesuatu sebelum indeks 4 lebih kecil atau sama dengan pivot, dan segala sesuatu mulai dari indeks 4 dan seterusnya lebih besar atau sama dengan pivot.

Berdasarkan panduan tersebut, Anda memerlukan kode untuk dua operasi: pertukaran.ping dua elemen dan partisi suatu rentang.

Code untuk Menukar Dua Numbers in JavaNaskah

Seperti yang ditunjukkan pada tangkapan layar editor di atas, helper swap menggunakan variabel sementara untuk menukar nilai pada dua indeks. Helper ini memodifikasi array secara langsung dan tidak mengembalikan apa pun.

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Keluaran:

[ 9, 3, 7, 6, 2, 5 ]

Code untuk Melakukan Partisi

Kode pada tangkapan layar di atas mengubah langkah 1 hingga 8 menjadi sebuah fungsi. Dua bagian dalam loop majukan penunjuknya, if Blok tersebut melakukan pertukaran, dan fungsi tersebut mengembalikan indeks pemisahan.

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;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Keluaran:

[ 5, 3, 2, 6, 7, 9 ]
4

Outputnya persis sama dengan panduan manual: setelah satu kali proses partisi, array menjadi [5,3,2,6,7,9] dan indeks pemisahan yang dikembalikan adalah 4.

Lakukan Rekursif Operaproduksi

Setelah partisi mengembalikan indeks pemisah, gunakan indeks tersebut untuk membagi rentang dan jalankan Quick Sort pada setiap bagian. Itulah mengapa algoritma ini disebut Divide and Conquer (Bagi dan Taklukkan). Rekursi berlanjut hingga setiap subrentang hanya berisi satu elemen, pada titik tersebut seluruh array telah terurut.

Catatan: Quick Sort bekerja pada array yang sama secara terus-menerus. Tidak ada array baru yang dibuat dalam proses ini, itulah yang menjadikannya algoritma in-place.

Jadi Anda menelepon partisi () fungsi yang dijelaskan di atas dan gunakan nilai kembaliannya untuk memisahkan susunan menjadi beberapa bagian. Berikut kode yang melakukannya:

Perhatikan dua kondisi penjaga yang disorot pada tangkapan layar. left < index - 1 menegaskan bahwa setidaknya dua elemen tersisa di sisi kiri, dan index < right Hal yang sama berlaku untuk sisi kanan. Tanpa pengaman tersebut, fungsi akan memanggil dirinya sendiri selamanya pada rentang elemen tunggal.

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 items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Keluaran:

[ 2, 3, 5, 6, 7, 9 ]

Selesaikan Pengurutan Cepat Code

Dengan menggabungkan bagian pertukaran (swap), partisi, dan rekursi, maka implementasi lengkapnya adalah:

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); // swapping 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);

Keluaran:

[ 2, 3, 5, 6, 7, 9 ]

Tangkapan layar di atas menunjukkan program lengkap di editor beserta array yang sudah diurutkan di konsol. Implementasi ini telah diverifikasi terhadap array yang sudah diurutkan, array yang diurutkan terbalik, array yang berisi nilai duplikat dan identik, angka negatif, elemen tunggal, dan array kosong, dan menghasilkan hasil yang benar dalam setiap kasus.

Kompleksitas Waktu dan Ruang dari Quick Sort

Setiap proses partisi menyentuh setiap elemen dalam rentang sekali, sehingga satu proses membutuhkan biaya O(n). Oleh karena itu, total biaya bergantung pada berapa kali array dapat dibagi sebelum rentang menjadi trivial.

Kompleksitas ruangnya adalah O(log n) Untuk versi in-place ini. Tidak ada array kedua yang dialokasikan, sehingga satu-satunya memori tambahan adalah tumpukan rekursi, dan pemisahan seimbang menjaga tumpukan tersebut tetap sedalam sekitar log₂(n) frame. Dalam kasus terburuk yang degeneratif, tumpukan tumbuh menjadi O(n) frame, itulah sebabnya array yang sangat besar dapat menyebabkan luapan tumpukan panggilan.

Dua angka membuat hal ini konkret. Mengurutkan 4,096 nilai acak dengan kode di atas menggunakan sekitar 65,000 perbandingan terhadap n·log₂(n) teoritis sebesar 49,152, dan rekursi terdalam mencapai 24 frame sementara log₂(4096) adalah 12. Kedua angka tersebut berada dalam faktor konstanta kecil yang diharapkan dari algoritma O(n log n).

Pengurutan Cepat vs Pengurutan Lainnya Algorithms

Quick Sort jarang menjadi satu-satunya pilihan. Tabel di bawah ini membandingkannya dengan algoritma lain yang kemungkinan besar akan Anda temui, sehingga Anda dapat memilih algoritma yang tepat untuk data Anda.

Quick Sort biasanya lebih unggul dalam praktiknya karena loop dalamnya ringkas dan bekerja pada rentang berurutan yang ramah cache. Pilih merge sort ketika Anda membutuhkan batasan O(n log n) yang terjamin atau pengurutan yang stabil, heap sort ketika memori sangat terbatas, dan insertion sort untuk array yang sangat kecil atau hampir terurut. Pustaka produksi sering menggabungkannya: introsort dimulai dengan Quick Sort, beralih ke heap sort jika rekursi terlalu dalam, dan diakhiri dengan insertion sort pada rentang kecil.

Cara Mengurutkan Objek dan String dengan Cepat

Implementasi yang ditunjukkan sejauh ini membandingkan nilai dengan < ke >, yang membatasinya hanya pada angka. Aplikasi sebenarnya perlu mengurutkan objek berdasarkan properti, string secara alfabetis, atau tanggal secara kronologis. Solusinya adalah memindahkan perbandingan ke dalam fungsi callback, persis seperti fungsi bawaan. sort() tidak.

Sebuah fungsi pembanding menerima dua nilai dan mengembalikan angka negatif ketika nilai pertama seharusnya lebih dulu, angka positif ketika nilai kedua seharusnya lebih dulu, dan nol ketika keduanya setara. Mengganti dua perbandingan yang dikodekan secara langsung dengan panggilan fungsi pembanding membuat algoritma ini bekerja pada tipe data apa pun.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Keluaran:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Ada tiga detail yang perlu diperhatikan. Penjaga rekursi sekarang left >= right, yang berlaku untuk rentang apa pun dan tidak bergantung pada panjang array luar. Perbandingan string menggunakan localeCompare() agar karakter beraksen dan huruf besar/kecil ditangani dengan benar, bukan berdasarkan titik kode mentah. Dan karena Quick Sort tidak stabil, catatan yang memiliki gaji yang sama mungkin bertukar tempat; urutkan berdasarkan kunci kedua sebagai penentu urutan jika urutan asli penting bagi Anda.

Siap untuk melanjutkan? Perkuat dasar-dasarnya dengan JavaPengantar naskah, berlatih mekanika penunjuk di JavaPerulangan skrip, kerjakan lebih lanjut praktis JavaContoh kode skrip, bandingkan implementasinya di Penyisipan Sortir ke Urutan Heapatau menambahkan tipe statis ke algoritma ini dengan TypeScript referensi.

Pertanyaan Umum Demo Slot