5 Algoritma Sorting Penting Wajib Tahu!
Dalam dunia pemrograman, mengurutkan data adalah tugas fundamental. Entah Anda sedang mengatur daftar nama berdasarkan abjad, mengurutkan harga produk dari termurah hingga termahal, atau mengoptimalkan pencarian dalam database yang besar, algoritma pengurutan memainkan peran penting. Efisiensi algoritma pengurutan secara signifikan mempengaruhi kinerja aplikasi Anda, terutama saat berhadapan dengan dataset yang besar. Artikel ini akan membahas lima algoritma pengurutan yang penting dan wajib Anda ketahui, termasuk cara kerjanya, kompleksitas waktunya, dan kapan sebaiknya digunakan.
1. Bubble Sort: Sederhana Namun Kurang Efisien
Bubble Sort adalah algoritma pengurutan paling sederhana untuk dipahami. Cara kerjanya adalah dengan berulang kali membandingkan pasangan elemen yang berdekatan dan menukar posisinya jika urutannya salah. Proses ini diulang dari awal array hingga tidak ada lagi pertukaran yang diperlukan, menandakan bahwa array telah diurutkan.
Cara Kerja:
Bayangkan Anda memiliki deretan gelembung dengan ukuran yang berbeda. Setiap kali Anda mengocok deretan itu, gelembung yang lebih besar (elemen yang lebih besar dalam array) akan naik ke atas (ujung array) karena bertukar posisi dengan gelembung yang lebih kecil di bawahnya. Proses ini terus berulang sampai semua gelembung terurut berdasarkan ukurannya.
Contoh:
Misalkan kita memiliki array [5, 1, 4, 2, 8].
- Iterasi 1: (5, 1, 4, 2, 8) -> (1, 5, 4, 2, 8) -> (1, 4, 5, 2, 8) -> (1, 4, 2, 5, 8) -> (1, 4, 2, 5, 8)
- Iterasi 2: (1, 4, 2, 5, 8) -> (1, 4, 2, 5, 8) -> (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8)
- Iterasi 3: (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8)
- Iterasi 4: (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8)
Kompleksitas Waktu:
- Best Case: O(n) – terjadi ketika array sudah terurut.
- Average Case: O(n^2)
- Worst Case: O(n^2)
Kapan Menggunakan:
Bubble Sort sebaiknya hanya digunakan untuk array yang sangat kecil atau untuk tujuan pendidikan karena kompleksitas waktunya yang kuadratik membuatnya tidak efisien untuk dataset yang besar.
2. Insertion Sort: Mirip Mengurutkan Kartu
Insertion Sort bekerja dengan cara yang mirip dengan cara Anda mengurutkan kartu di tangan Anda. Algoritma ini membagi array menjadi dua bagian: bagian yang sudah diurutkan dan bagian yang belum diurutkan. Algoritma kemudian memilih elemen dari bagian yang belum diurutkan dan menempatkannya pada posisi yang tepat di bagian yang sudah diurutkan.
Cara Kerja:
Ambil elemen pertama dari bagian yang belum diurutkan. Bandingkan elemen ini dengan elemen-elemen di bagian yang sudah diurutkan, mulai dari yang paling kanan. Jika elemen yang dibandingkan lebih besar dari elemen yang sedang disisipkan, geser elemen tersebut ke kanan. Lanjutkan proses ini sampai Anda menemukan posisi yang tepat untuk elemen yang sedang disisipkan.
Contoh:
Misalkan kita memiliki array [5, 1, 4, 2, 8].
- [5] 1, 4, 2, 8 -> [1, 5] 4, 2, 8
- [1, 5] 4, 2, 8 -> [1, 4, 5] 2, 8
- [1, 4, 5] 2, 8 -> [1, 2, 4, 5] 8
- [1, 2, 4, 5] 8 -> [1, 2, 4, 5, 8]
Kompleksitas Waktu:
- Best Case: O(n) – terjadi ketika array sudah terurut.
- Average Case: O(n^2)
- Worst Case: O(n^2)
Kapan Menggunakan:
Insertion Sort efisien untuk array kecil atau array yang hampir terurut. Ia juga merupakan algoritma pengurutan in-place yang berarti ia tidak memerlukan memori tambahan yang signifikan.
3. Selection Sort: Mencari yang Terkecil
Selection Sort bekerja dengan berulang kali mencari elemen terkecil dari bagian yang belum diurutkan dan menukarnya dengan elemen pertama dari bagian tersebut. Proses ini terus diulang sampai seluruh array terurut.
Cara Kerja:
Cari elemen terkecil dalam array. Tukar elemen terkecil ini dengan elemen pertama dalam array. Kemudian, cari elemen terkecil berikutnya (dari elemen kedua hingga akhir array) dan tukar dengan elemen kedua. Ulangi proses ini sampai semua elemen terurut.
Contoh:
Misalkan kita memiliki array [5, 1, 4, 2, 8].
- [5, 1, 4, 2, 8] -> [1, 5, 4, 2, 8] (Tukar 5 dengan 1)
- [1, 5, 4, 2, 8] -> [1, 2, 4, 5, 8] (Tukar 5 dengan 2)
- [1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] (Tidak ada pertukaran karena 4 sudah berada di posisi yang benar)
- [1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] (Tidak ada pertukaran karena 5 sudah berada di posisi yang benar)
Kompleksitas Waktu:
- Best Case: O(n^2)
- Average Case: O(n^2)
- Worst Case: O(n^2)
Kapan Menggunakan:
Selection Sort memiliki kompleksitas waktu yang selalu O(n^2), sehingga kurang efisien dibandingkan algoritma pengurutan lain untuk dataset yang besar. Namun, ia meminimalkan jumlah pertukaran, yang bisa menjadi keuntungan dalam situasi tertentu di mana biaya pertukaran sangat tinggi.
4. Merge Sort: Divide and Conquer
Merge Sort adalah algoritma pengurutan yang menggunakan pendekatan divide and conquer. Algoritma ini membagi array menjadi dua bagian yang sama besar, kemudian mengurutkan masing-masing bagian secara rekursif, dan akhirnya menggabungkan kedua bagian yang sudah diurutkan menjadi satu array yang terurut.
Cara Kerja:
- Divide: Bagi array menjadi dua bagian yang sama besar.
- Conquer: Urutkan masing-masing bagian secara rekursif menggunakan Merge Sort.
- Combine: Gabungkan (merge) kedua bagian yang sudah diurutkan menjadi satu array yang terurut.
Contoh:
Misalkan kita memiliki array [5, 1, 4, 2, 8].
- Divide: [5, 1, 4], [2, 8]
- Conquer:
- [5, 1, 4] -> [5], [1, 4] -> [5], [1], [4] -> [1, 5], [4] -> [1, 4, 5]
- [2, 8] -> [2], [8] -> [2, 8]
- Combine: [1, 4, 5], [2, 8] -> [1, 2, 4, 5, 8]
Kompleksitas Waktu:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Kapan Menggunakan:
Merge Sort adalah algoritma pengurutan yang efisien untuk dataset yang besar. Kompleksitas waktunya yang O(n log n) membuatnya lebih cepat dibandingkan algoritma pengurutan kuadratik (O(n^2)) seperti Bubble Sort, Insertion Sort, dan Selection Sort. Namun, Merge Sort memerlukan memori tambahan untuk menyimpan bagian array selama proses penggabungan.
5. Quick Sort: Pilihan Populer
Quick Sort juga merupakan algoritma pengurutan yang menggunakan pendekatan divide and conquer. Algoritma ini memilih satu elemen sebagai pivot, kemudian mempartisi array sedemikian rupa sehingga semua elemen yang lebih kecil dari pivot berada di sebelah kiri pivot, dan semua elemen yang lebih besar dari pivot berada di sebelah kanan pivot. Algoritma kemudian secara rekursif mengurutkan bagian kiri dan kanan pivot.
Cara Kerja:
- Pilih Pivot: Pilih sebuah elemen sebagai pivot (misalnya, elemen pertama, elemen terakhir, atau elemen acak).
- Partitioning: Atur ulang array sedemikian rupa sehingga semua elemen yang lebih kecil dari pivot berada di sebelah kiri pivot, dan semua elemen yang lebih besar dari pivot berada di sebelah kanan pivot.
- Rekursi: Urutkan secara rekursif bagian kiri dan kanan pivot menggunakan Quick Sort.
Contoh:
Misalkan kita memiliki array [5, 1, 4, 2, 8] dan memilih 5 sebagai pivot.
- Partitioning: [1, 4, 2, 5, 8] (Elemen yang lebih kecil dari 5 berada di sebelah kiri, elemen yang lebih besar dari 5 berada di sebelah kanan)
- Rekursi:
- [1, 4, 2] -> Quick Sort
- [8] -> Sudah terurut
Kompleksitas Waktu:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n^2) – terjadi ketika pivot selalu merupakan elemen terkecil atau terbesar.
Kapan Menggunakan:
Quick Sort adalah salah satu algoritma pengurutan yang paling populer karena efisiensinya yang tinggi pada rata-rata kasus. Kompleksitas waktunya yang O(n log n) membuatnya cepat, dan ia merupakan algoritma in-place (memerlukan memori tambahan yang kecil). Namun, kinerja Quick Sort sangat bergantung pada pemilihan pivot. Pemilihan pivot yang buruk dapat menyebabkan kompleksitas waktu menjadi O(n^2).
Kesimpulan
Memahami berbagai algoritma pengurutan adalah keterampilan penting bagi setiap programmer. Meskipun Bubble Sort mudah dipahami, efisiensinya sangat terbatas. Insertion Sort berguna untuk array kecil atau hampir terurut. Selection Sort meminimalkan pertukaran. Merge Sort dan Quick Sort menawarkan kinerja O(n log n) yang lebih baik, namun dengan trade-off yang berbeda (memori tambahan untuk Merge Sort, pemilihan pivot untuk Quick Sort). Pemilihan algoritma yang tepat bergantung pada ukuran dataset, karakteristik data, dan batasan sumber daya. Dengan memahami karakteristik masing-masing algoritma, Anda dapat membuat keputusan yang lebih baik dan mengoptimalkan kinerja aplikasi Anda. Eksperimenlah dengan berbagai algoritma pengurutan untuk merasakan langsung perbedaannya dan mengidentifikasi mana yang paling cocok untuk kebutuhan spesifik Anda.
