**Pendahuluan**
Sorting (pengurutan) adalah konsep fundamental dalam ilmu komputer yang penting dipahami setiap programmer. Artikel ini akan membahas empat algoritma sorting klasik - Bubble Sort, Selection Sort, Insertion Sort, dan Shell Sort - beserta implementasinya dalam Python. Kami akan menjelaskan konsep dasar, kompleksitas waktu, serta contoh kode yang mudah dipahami pemula.
---
### **1. Bubble Sort**
**Konsep Dasar:**
Membandingkan dan menukar elemen bersebelahan secara berulang hingga semua terurut
**Implementasi Kode:**
```python
def bubblesort(alist):
for i in range(0, len(alist)-1):
for j in range(len(alist)-1, i, -1):
if alist[j] < alist[j-1]:
# Tukar posisi
alist[j], alist[j-1] = alist[j-1], alist[j]
```
**Penjelasan Langkah:**
1. Iterasi dari akhir ke awal list
2. Bandingkan elemen berdekatan
3. Jika elemen lebih kecil, lakukan swap
4. Ulangi hingga seluruh list terurut
**Kompleksitas Waktu:**
- Worst Case: O(n²)
- Best Case: O(n) (jika list sudah terurut)
**Visualisasi:**
```
[5, 3, 8, 6] → [3, 5, 6, 8]
```
---
### **2. Selection Sort**
**Konsep Dasar:**
Memilih elemen terkecil dan menukarnya dengan elemen di posisi awal
**Implementasi Kode:**
```python
def selectionsort(alist):
for i in range(0, len(alist)-1):
minposition = len(alist)-1
for j in range(len(alist)-2, i-1, -1):
if alist[j] < alist[minposition]:
minposition = j
# Tukar dengan posisi terkini
alist[i], alist[minposition] = alist[minposition], alist[i]
```
**Penjelasan Langkah:**
1. Cari elemen terkecil di sublist
2. Tukar dengan elemen pertama di sublist
3. Geser batas sublist yang belum diurutkan
**Kompleksitas Waktu:**
- Selalu O(n²)
**Contoh Eksekusi:**
```
[29, 10, 14, 37] → [10, 14, 29, 37]
```
---
### **3. Insertion Sort**
**Konsep Dasar:**
Membangun list terurut dengan menyisipkan satu elemen sekaligus ke posisi yang benar
**Implementasi Kode:**
```python
def insertionsort(alist):
for i in range(1, len(alist)):
currentvalue = alist[i]
position = i
# Geser elemen lebih besar ke kanan
while position > 0 and alist[position-1] > currentvalue:
alist[position] = alist[position-1]
position -= 1
alist[position] = currentvalue
```
**Penjelasan Langkah:**
1. Ambil elemen dari list belum terurut
2. Bandingkan dengan elemen di list terurut
3. Sisipkan di posisi yang tepat
**Kompleksitas Waktu:**
- Worst Case: O(n²)
- Best Case: O(n)
**Analog:**
Seperti mengurutkan kartu di tangan
---
### **4. Shell Sort**
**Konsep Dasar:**
Optimisasi Insertion Sort dengan membagi list menjadi sublist menggunakan interval (gap)
**Implementasi Kode:**
```python
def shellsort(alist):
def insort(alist, start, step):
for i in range(start+step, len(alist), step):
currentvalue = alist[i]
position = i
while position >= step and alist[position-step] > currentvalue:
alist[position] = alist[position-step]
position -= step
alist[position] = currentvalue
step = len(alist) // 2
while step > 0:
for i in range(step):
insort(alist, i, step)
step = step // 2
```
**Penjelasan Langkah:**
1. Bagi list dengan gap tertentu
2. Lakukan Insertion Sort pada setiap sublist
3. Kurangi gap secara bertahap hingga 1
**Kompleksitas Waktu:**
- Bergantung pada sequence gap
- Rata-rata: O(n log n)
**Contoh Gap Sequence:**
```
8 → 4 → 2 → 1
```
---
### **Perbandingan Algoritma**
| Algoritma | Best Case | Average Case | Worst Case | Stabil | In-place |
|----------------|-----------|--------------|------------|--------|----------|
| Bubble Sort | O(n) | O(n²) | O(n²) | Ya | Ya |
| Selection Sort | O(n²) | O(n²) | O(n²) | Tidak | Ya |
| Insertion Sort | O(n) | O(n²) | O(n²) | Ya | Ya |
| Shell Sort | O(n log n)| O(n log² n) | O(n²) | Tidak | Ya |
---
### **Kapan Menggunakan?**
1. **Bubble Sort**: Untuk list kecil atau pengenalan konsep sorting
2. **Selection Sort**: Jika operasi swap mahal secara komputasi
3. **Insertion Sort**: Untuk data hampir terurut atau kecil
4. **Shell Sort**: Peningkatan performa Insertion Sort untuk data sedang
---
### **Kesimpulan**
Keempat algoritma ini merupakan dasar penting dalam memahami teknik sorting. Meskipun tidak efisien untuk dataset besar (lebih baik menggunakan Quick/Merge Sort), pemahaman konsep ini sangat penting untuk:
- Memahami dasar algoritma sorting
- Menganalisis kompleksitas waktu
- Memilih algoritma yang tepat untuk kasus spesifik
**Latihan:** Coba implementasikan algoritma ini untuk mengurutkan data berikut:
`[23, 7, 42, 15, 31, 5, 19]` dan hitung jumlah operasi swap yang dilakukan!
---
**Referensi Lanjutan:**
- [Visualisasi Algoritma Sorting](https://www.toptal.com/developers/sorting-algorithms)
- [Analysis of Shellsort](https://cs.stackexchange.com/questions/3112)
Komentar
Posting Komentar