SORTING

1. Bubble Sort

Bubble Sort adalah algoritma pengurutan paling sederhana yang bekerja dengan cara
membandingkan dua elemen yang berdekatan dan menukarnya jika urutan mereka salah.
Proses ini diulang hingga dak ada lagi elemen yang perlu ditukar. Elemen terbesar akan
"menggelembung" (bubble up) ke posisi akhir pada se ap iterasi.

 Ide Utama: Membandingkan dan menukar elemen yang bersebelahan.

 Keunggulan: Sangat mudah dipahami dan diimplementasikan.

 Kelemahan: Sangat dak efisien untuk data dalam jumlah besar karena memiliki
kompleksitas waktu O(n^2).

Contoh Langkah-langkah (Array: [5, 1, 4, 2])

Iterasi Array Awal Langkah-langkah Array Akhir

1 [5, 1, 4, 2] Bandingkan 5 dan 1. Tukar. [1, 5, 4, 2]
[1, 5, 4, 2] Bandingkan 5 dan 4. Tukar. [1, 4, 5, 2]
[1, 4, 5, 2] Bandingkan 5 dan 2. Tukar. [1, 4, 2, 5]
2 [1, 4, 2, 5] Bandingkan 4 dan 2. Tukar. [1, 2, 4, 5]
[1, 2, 4, 5] Bandingkan 4 dan 5. Tidak perlu tukar. [1, 2, 4, 5]
3 [1, 2, 4, 5] Tidak ada lagi yang perlu ditukar, array sudah terurut. [1, 2, 4, 5]

Bayangkan Anda sedang mengantre di sebuah toko dengan teman-teman Anda. Anda ingin
mengurutkan antrean dari yang ter nggi hingga terpendek.

 Langkah: Anda mulai dari ujung antrean dan membandingkan nggi Anda dengan
orang di sebelah Anda. Jika Anda lebih pendek, Anda bertukar posisi. Lalu Anda maju
ke orang berikutnya dan melakukan hal yang sama. Proses ini diulang terus-menerus
hingga dak ada lagi orang yang perlu bertukar posisi.

 Analogi: Se ap perbandingan dan pertukaran adalah langkah kecil yang

"menggelembungkan" orang ter nggi ke posisi belakang antrean. Prosesnya lambat,
tapi pas .

2. Selec on Sort

Selec on Sort bekerja dengan cara memilih elemen terkecil dari bagian array yang belum
terurut dan menempatkannya di awal. Proses ini diulang untuk se ap elemen hingga seluruh
array terurut.
  Ide Utama: Mencari elemen terkecil dan menempatkannya di posisi yang benar.

 Keunggulan: Jumlah pertukaran data (swap) yang dilakukan minimal.

 Kelemahan: Juga memiliki kompleksitas waktu O(n^2), kurang efisien untuk data
besar.

Contoh Langkah-langkah (Array: [6, 4, 1, 8])

Iterasi Array Awal Langkah-langkah Array Akhir

1 [6, 4, 1, 8] Cari elemen terkecil. Yaitu 1. [1, 4, 6, 8]
Tukar 1 dengan 6 (elemen di posisi pertama). [1, 4, 6, 8]
2 [1, 4, 6, 8] Cari elemen terkecil dari sisa array. Yaitu 4. [1, 4, 6, 8]
4 sudah di posisi yang benar. Tidak perlu tukar. [1, 4, 6, 8]
3 [1, 4, 6, 8] Cari elemen terkecil dari sisa array. Yaitu 6. [1, 4, 6, 8]
6 sudah di posisi yang benar. Tidak perlu tukar. [1, 4, 6, 8]

Bayangkan Anda sedang merapikan rak buku, dan ingin mengurutkan buku dari yang paling
pis hingga paling tebal.

 Langkah: Pertama, Anda mencari buku paling pis di seluruh rak. Setelah
menemukannya, Anda menukarnya dengan buku pertama di rak. Lalu, Anda mencari
buku paling pis di sisa rak (mulai dari buku kedua) dan menukarnya dengan buku
kedua. Begitu seterusnya sampai semua buku terurut.

 Analogi: Anda secara selek f memilih (select) elemen terkecil dan menempatkannya
di posisi yang benar. Proses ini memakan waktu karena Anda harus memeriksa seluruh
sisa rak se ap kali.

3. Inser on Sort

Inser on Sort mengurutkan array dengan mengambil satu elemen pada satu waktu dan
menyisipkannya (insert) ke posisi yang benar dalam sub-array yang sudah terurut. Mirip
seper cara kita mengurutkan kartu di tangan.

 Ide Utama: Menyisipkan elemen ke dalam sub-array yang sudah terurut.

 Keunggulan: Sangat efisien untuk array yang sudah hampir terurut.

 Kelemahan: Kompleksitas waktu O(n^2), dak efisien untuk data yang dak terurut
dengan baik.

Contoh Langkah-langkah (Array: [5, 1, 4, 2])

Iterasi Array Awal Langkah-langkah Array Akhir
1 [5], 1, 4, 2 Ambil 1. Sisipkan ke kiri 5. [1, 5], 4, 2
2 [1, 5], 4, 2 Ambil 4. Sisipkan di antara 1 dan 5. [1, 4, 5], 2
3 [1, 4, 5], 2 Ambil 2. Sisipkan di antara 1 dan 4. [1, 2, 4, 5]
Final [1, 2, 4, 5] Array sudah terurut. [1, 2, 4, 5]

Bayangkan Anda sedang memegang setumpuk kartu remi yang dak terurut. Anda ingin
mengurutkannya dari As hingga Raja.

 Langkah: Anda mengambil satu kartu dari tumpukan yang dak terurut. Kemudian,
Anda melihat kartu-kartu yang sudah ada di tangan Anda (yang sudah terurut) dan
menyisipkan (insert) kartu baru tersebut di posisi yang benar. Anda mengulanginya
untuk se ap kartu dari tumpukan.

 Analogi: Prosesnya efisien jika kartu sudah sedikit terurut, karena Anda dak perlu
memindahkan banyak kartu. Tapi jika tumpukannya sangat acak, proses ini bisa jadi
lebih lambat.

4. Merge Sort

Merge Sort adalah algoritma pengurutan yang efisien dan berbasis divide and conquer (bagi
dan taklukkan). Algoritma ini membagi array menjadi dua bagian hingga hanya tersisa satu
elemen, lalu menggabungkan (merge) kembali bagian-bagian tersebut secara terurut.

 Ide Utama: Membagi array menjadi sub-array terkecil, lalu menggabungkannya

kembali secara terurut.

 Keunggulan: Sangat efisien, dengan kompleksitas waktu O(n log n), dan stabil.

 Kelemahan: Membutuhkan memori tambahan untuk menyimpan sub-array.

Contoh Langkah-langkah (Array: [8, 3, 1, 7])

Fase Aksi Array

1. Bagi (Divide) Bagi menjadi 2 sub-array [8, 3] dan [1, 7]
Bagi lagi [8], [3] dan [1], [7]
2. Gabung (Merge) Gabungkan [8] dan [3] secara terurut [3, 8]
Gabungkan [1] dan [7] secara terurut [1, 7]
Gabungkan [3, 8] dan [1, 7] secara terurut [1, 3, 7, 8]
Bayangkan Anda punya dua tumpukan kertas yang terpisah, satu tumpukan berisi nama-nama
orang yang sudah terurut, dan satu lagi dak. Anda ingin menggabungkannya menjadi satu
tumpukan yang rapi.

 Langkah: Untuk mengurutkan tumpukan yang besar, Anda membaginya menjadi dua
tumpukan yang lebih kecil. Masing-masing tumpukan kecil ini dibagi lagi hingga hanya
ada satu kertas di se ap tumpukan. Setelah itu, Anda mulai menggabungkan (merge)
kembali tumpukan-tumpukan itu, sambil memas kan se ap tumpukan yang
digabungkan sudah dalam urutan yang benar.

 Analogi: Ini seper membagi tugas besar menjadi tugas-tugas kecil yang lebih mudah,
lalu menggabungkannya kembali secara teratur.

5. Quick Sort

Quick Sort juga merupakan algoritma divide and conquer. Algoritma ini memilih sebuah
elemen yang disebut pivot, lalu mempar si array menjadi dua sub-array: elemen yang lebih
kecil dari pivot dan elemen yang lebih besar dari pivot. Proses ini diulang secara rekursif hingga
seluruh array terurut.

 Ide Utama: Memilih pivot dan mempar si array.

 Keunggulan: Salah satu algoritma tercepat dengan kompleksitas waktu rata-rata O(n
log n).

 Kelemahan: Kompleksitas terburuknya adalah O(n^2), terjadi saat pemilihan pivot

kurang tepat (misalnya, selalu memilih elemen terkecil/terbesar).

Contoh Langkah-langkah (Array: [7, 2, 1, 6])

Array Array
Iterasi Langkah-langkah
Awal Akhir
1 [7, 2, 1, 6] Pilih pivot (6).
Par si array: pindahkan semua elemen <6 ke kiri dan >6 ke
[2, 1, 6, 7]
kanan.
2 [2, 1] Par si sub-array kiri dengan pivot 2.
Tukar 2 dan 1. [1, 2]
3 [7] Sub-array kanan sudah terurut. [7]
Final [1, 2, 6, 7] Gabungkan semua bagian. [1, 2, 6, 7]

Bayangkan Anda adalah seorang guru dan ingin memisahkan siswa di kelas menjadi dua
kelompok: yang mendapatkan nilai di atas 70 dan di bawah 70.
  Langkah: Anda menunjuk satu siswa sebagai "patokan" atau pivot. Lalu Anda meminta
semua siswa dengan nilai di bawah nilai pivot untuk berkumpul di sisi kiri kelas, dan
yang di atas nilai pivot di sisi kanan. Setelah itu, Anda melakukan hal yang sama di
se ap kelompok kecil yang terbentuk.

 Analogi: Strategi ini adalah "bagi dan taklukkan". Anda memisahkan masalah besar
menjadi masalah yang lebih kecil, lalu menyelesaikan masalah-masalah kecil tersebut
secara terpisah, hingga semua siswa terurut berdasarkan nilai mereka.

Tabel Perbandingan Singkat

Fitur Bubble Sort Selec on Sort Inser on Sort Merge Sort Quick Sort
Kompleksitas Waktu O(n^2) O(n^2) O(n^2) O(n log n) O(n log n)
Kompleksitas Ruang O(1) O(1) O(1) O(n) O(log n)
Stabilitas Stabil Tidak Stabil Stabil Stabil Tidak Stabil
Waktu Terbaik O(n) O(n^2) O(n) O(n log n) O(n log n)