quicksort javascript

2 min read 03-10-2024

Pengenalan

Quicksort adalah salah satu algoritma pengurutan yang paling efisien dan banyak digunakan dalam pengembangan perangkat lunak. Algoritma ini bekerja dengan menggunakan pendekatan divide and conquer, yang membagi array menjadi bagian yang lebih kecil dan mengurutkannya secara rekursif. Dalam artikel ini, kita akan membahas bagaimana cara mengimplementasikan algoritma Quicksort di JavaScript dan memberikan beberapa analisis mengenai performanya.

Kode Asli Quicksort dalam JavaScript

Berikut adalah contoh kode Quicksort sederhana dalam JavaScript:

function quicksort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return [...quicksort(left), pivot, ...quicksort(right)];
}

const array = [3, 6, 8, 10, 1, 2, 1];
const sortedArray = quicksort(array);
console.log(sortedArray);

Memahami Kode Quicksort

Dalam kode di atas, fungsi quicksort menerima sebuah array sebagai argumen. Berikut adalah langkah-langkah yang diambil dalam algoritma ini:

Basis Rekursif: Jika panjang array kurang dari atau sama dengan 1, maka array tersebut sudah terurut dan akan dikembalikan.
Pivot: Elemen terakhir dari array dipilih sebagai pivot. Elemen ini digunakan untuk membagi array menjadi dua bagian.
Pembagian Array: Elemen-elemen dalam array dibandingkan dengan pivot. Elemen yang lebih kecil dari pivot dimasukkan ke dalam array left, sedangkan yang lebih besar atau sama dimasukkan ke dalam array right.
Rekursi: Fungsi quicksort dipanggil secara rekursif untuk kedua array left dan right, dan akhirnya mengembalikan array yang terurut dengan menyatukan hasilnya dengan pivot.

Analisis dan Penjelasan

Kompleksitas Waktu

Keunggulan utama dari algoritma Quicksort adalah kecepatan dalam pengurutan. Rata-rata kompleksitas waktu untuk Quicksort adalah O(n log n), tetapi dalam kasus terburuk, kompleksitasnya dapat menjadi O(n²). Hal ini dapat terjadi ketika pivot yang dipilih adalah elemen terkecil atau terbesar berulang kali.

Penggunaan Memori

Quicksort juga memiliki keunggulan dalam penggunaan memori. Ini adalah algoritma in-place, yang berarti ia tidak memerlukan array tambahan yang besar seperti beberapa algoritma pengurutan lainnya. Quicksort menggunakan stack untuk menyimpan hasil rekursi, yang membuatnya lebih efisien dalam penggunaan memori.

Contoh Praktis

Sebagai contoh, jika kita memiliki array berikut:

const unsortedArray = [4, 2, 7, 1, 3];
const sorted = quicksort(unsortedArray);
console.log(sorted); // Output: [1, 2, 3, 4, 7]

Dengan menggunakan algoritma Quicksort yang kita implementasikan, array yang tidak terurut tersebut akan terurut dengan cepat.

Kesimpulan

Quicksort adalah algoritma pengurutan yang efektif dan efisien yang sangat berguna dalam pengembangan perangkat lunak. Dengan memanfaatkan pendekatan divide and conquer, Quicksort dapat mengurutkan array dengan cepat sambil menjaga penggunaan memori yang rendah.

Jika Anda ingin memperdalam pemahaman tentang algoritma pengurutan dan Quicksort, berikut adalah beberapa sumber daya yang bermanfaat:

Dengan demikian, pemahaman yang kuat tentang Quicksort dapat membantu Anda dalam menulis kode yang lebih efisien dan efektif di dunia pemrograman JavaScript.