Algoritma Quick Sort Dengan Recursive

Sorting adalah bagian yang sangat penting dalam pemrograman. Dengan sorting, kita bisa melakukan beberapa hal yang sangat krusial seperti menampilkan data secara berurutan, pembuatan keputusan, pencarian data, dan sebagainya. Dalam pelajaran algoritma, metode untuk melakukan sorting sangatlah banyak. Di antaranya adalah bubble sort, merge sort, insertion sort, heap sort, selection sort, shell sort, dan quick sort.

Mengapa Harus Paham Algoritma Sorting?

Pertanyaan ini sering saya tanyakan, ada banyak bahasa pemrograman yang secara instan bisa melakukan sorting misalnya JavaScript dengan arr.sort() dan PHP dengan fungsi sort(). Namun mengapa kita harus mengetahui sorting secara manual? Jawabannya adalah :

1. Tidak semua bahasa pemrograman memiliki metode sorting bawaan. Misalnya C, C++, dan Java.
2. Dengan mengetahui algoritmanya, bisa mengasah kemampuan mana algoritma yang hemat memori dan waktu (space and time complexity) dan mana algoritma yang boros keduanya.

Algoritma Quick Sort

Menggunakan algoritma yang mudah, mungkin tidak masalah jika data yang kita urutkan sebanyak ratusan atau ribuan saja, tetapi akan menjadi masalah besar ketika data yang harus diurutkan sangat banyak. Di antara banyak algoritma sorting, quick sort adalah algoritma yang terbaik karena hemat memori dan waktu. Mari kita pelajari cara kerja algoritma ini!

Misal ada sebuah array dengan urutan berikut : [1, 4, 6, 9, 2, 5, 8, 7] yang akan kita ubah dari yang terkecil ke terbesar menjadi [1, 2, 4, 5, 6, 7, 8, 9].

Pertama, kita akan ambil satu angka sebagai pivot, biasanya saya menggunakan item terakhir sebagai pivot-nya. Dalam array tersebut pivot-nya adalah 7.

Kedua, kita akan buat 2 array baru bernama left dan right. Array left berfungsi untuk menyimpan angka yang lebih kecil dari 7, sedangkan array right berfungsi untuk menyimpan angka lebih besar dari 7.

Ketiga, setelah melakukan seleksi di atas, maka yang terjadi adalah array left berisi [1, 4, 6, 5, 2] dan array right berisi [8, 9].

Apa Selanjutnya?

Kita sudah melakukan penyortiran awal. Jika kita gabungkan array left + pivot + array right, maka array nya akan menjadi seperti ini: [1, 4, 6, 5, 2, 7, 8, 9].

Keempat, kita hanya perlu melakukan sorting ulang array left dengan array right dengan metode yang sama. Misalnya pivot dari array left adalah 2, maka ini akan membuat array left baru menjadi seperti ini [1, 2, 4, 6, 5]. Dan array right tidak perlu di sorting ulang karena urutannya sudah sesuai.

Menggunakan Recursive

Untuk melakukan sorting ulang pada left dan right, kita bisa menggunakan while atau recursive. Namun saya rasa recursive lebih simpel daripada while.