Jelaskan bubble sort, insertion sort, dan selection sort.

Question

Accepted Answer

Ini tiga algoritma pengurutan perbandingan **O(n²)** yang sederhana. Mereka lambat pada input besar tetapi mudah dipahami dan berguna untuk mengajarkan mekanika pengurutan.

## Cara setiap algoritma bekerja

- **Bubble sort:** menukar pasangan yang berdekatan dan tidak terurut berulang kali; nilai besar "menggelembung" ke akhir setiap kali.
- **Selection sort:** menemukan minimum dari bagian yang belum diurutkan dan menukarnya ke tempat yang tepat.
- **Insertion sort:** menambah awalan yang diurutkan dengan menyisipkan setiap elemen baru ke tempat yang benar.

## Contoh (insertion sort)

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # element to place
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # shift bigger elements right
            j -= 1
        arr[j + 1] = key              # drop key into the gap
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## Perbandingan

| Sort | Best | Worst | Stable | In-place |
|------|------|-------|--------|----------|
| Bubble | O(n) | O(n²) | Yes | Yes |
| Selection | O(n²) | O(n²) | No | Yes |
| Insertion | O(n) | O(n²) | Yes | Yes |

## Kapan digunakan / perangkap

Insertion sort benar-benar cepat untuk larik **kecil atau hampir terurut** dan digunakan dalam pengurutan hibrida. Hindari ketiganya pada data besar yang tidak terurut — gunakan pengurutan O(n log n) sebaliknya.

## Mengapa ini penting

Pengurutan ini membangun intuisi tentang invarian, pertukaran, dan stabilitas sebelum Anda mengatasi algoritma lanjutan.

Insertion sort khususnya muncul dalam pengurutan produksi (seperti Timsort) untuk sub-larik kecil.

Memahami mengapa mereka O(n²) membuat lompatan ke pengurutan O(n log n) bermakna.

Sort	Best	Worst	Stable	In-place
Bubble	O(n)	O(n²)	Yes	Yes
Selection	O(n²)	O(n²)	No	Yes
Insertion	O(n)	O(n²)	Yes	Yes