Sorting — Belajar Algoritma

Quick Sort

Quick Sort atau “pengurutan cepat” adalah salah satu algoritma sorting yang sangat populer, digunakan secara default oleh beberapa bahasa pemrograman seperti .sort() pada JavaScript dan sort() pada PHP. Algoritma ini memiliki kompleksitas O(n*log(n)).

Kelebihan Quick Sort

1. Cepat dalam Praktik: Sering lebih cepat daripada algoritma lain seperti merge sort karena cache yang lebih baik dan konstanta waktu yang rendah.
2. Efisien dalam Pembagian Data: Cocok untuk data yang sebagian sudah terurut.
3. In-Place Sorting: Menggunakan sedikit ruang tambahan (O(log n)).
4. Sederhana: Konsepnya mudah dipahami dan diimplementasikan.

Kekurangan Quick Sort

1. Kasus Terburuk O(n²): Terjadi jika pivot yang dipilih adalah elemen terkecil atau terbesar setiap saat, meski bisa diatasi dengan strategi pivot yang baik.
2. Tidak Stabil: Elemen dengan nilai yang sama mungkin tidak mempertahankan urutan relatifnya.
3. Rekursi Mendalam: Bisa menyebabkan stack overflow pada dataset yang sangat besar, meski bisa diatasi dengan versi non-rekursif.
4. Kinerja Buruk pada Data Terurut: Kinerjanya menurun jika data sudah hampir atau sepenuhnya terurut tanpa strategi pivot yang tepat.

Bagaimana Quick Sort Bekerja?

Cara kerja dari quick sort bisa dikatakan sederhana namun akan membingungkan bagi pemula, anggap kita akan memproses array [7,2,1,3,4,5,6] dengan quick sort:

1. Tentukan nilai pivot, biasanya adalah item yang berada di tengah. Item yang berada di tengah array di atas adalah angka 3, maka pivot-nya adalah 3.
2. Buat 2 array kosong, yaitu left untuk menyimpan nilai yang lebih kecil dari pivot, dan right untuk menyimpan nilai yang lebih besar dari pivot.
3. Bandingkan setiap item dari array dengan pivot, jika lebih kecil maka simpan di left, jika lebih besar maka simpan di right.
4. Tugas selanjutnya adalah melakukan ketiga hal tersebut untuk array left dan array right, lalu simpan pivot antara left dengan right. Untuk melakukan proses yang sama kita bisa memanfaatkan recursive.
5. Jika ingin mengurutkan dari besar ke kecil, maka array left untuk menyimpan angka yang lebih besar dari pivot, dan array right untuk menyimpan angka yang lebih kecil dari pivot.

Berikut adalah contoh dari penggunaan quick sort:

function quickSort(numbers: number[]): number[] {
    if (numbers.length < 2) {
        return numbers;
    }
    
    const pivot = numbers[Math.floor(numbers.length / 2)];
    const left = [];
    const right = [];

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

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

console.log(quickSort([7,2,1,3,4,5,6])); // should be 1,2,3,4,5,6,7

Bubble Sort

Bubble sort atau disebut dengan “pengurutan gelembung” adalah metode pengurutan yang paling sederhana dibandingkan yang lain, biasanya dijadikan oleh para pemula sebagai referensi belajar.

Kelebihan Bubble Sort

1. Sederhana: Mudah dipahami dan diimplementasikan.
2. In-Place Sorting: Tidak memerlukan ruang tambahan yang signifikan (O(1)).
3. Stabil: Menjaga urutan relatif elemen dengan nilai yang sama.
4. Deteksi Data Terurut: Dapat mendeteksi jika data sudah terurut dan berhenti lebih awal.

Kekurangan Bubble Sort

1. Lambat untuk Data Besar: Kompleksitas waktu rata-rata dan terburuk adalah O(n²), tidak efisien untuk dataset besar.
2. Banyak Pertukaran: Melibatkan banyak pertukaran yang membuatnya lebih lambat dibanding algoritma lain seperti quick sort atau merge sort.
3. Tidak Efisien: Kinerja yang buruk dibandingkan algoritma pengurutan lainnya untuk sebagian besar kasus praktis.

Bagaimana Bubble Sort Bekerja?

1. Buat pengulangan (for) dimulai dari 0 sampai total array-1, biasanya menggunakan variabel i.
2. Buat pengulangan kedua di dalam pengulangan pertama dimulai dari current index sampai total array-1, biasanya menggunakan variabel j.
3. Bandingkan nilai dari numbers[i] dengan numbers[j]. Jika numbers[j] lebih kecil daripada numbers[i], maka tukar posisinya (swap). Jangan lupa untuk menyimpan numbers[i] ke dalam variabel baru (biasanya temp) agar tidak hilang ketika ditimpa dan bisa digunakan untuk menimpa numbers[j].

Berikut adalah contoh penggunaan bubble sort:

function bubbleSort(numbers: number[]): number[] {

    for (let i = 0; i < numbers.length; i++) {
        for (let j = i; j < numbers.length; j++) {
            if (numbers[i] > numbers[j]) {
                const temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
            }
        }
    }

    return numbers;
}

console.log(bubbleSort([5,2,4,1,3,6,7])); // should be 1,2,3,4,5,6,7