Tracing Bubble, Selection, Insertion Sort: Hitung Swap per Pass

Tracing bubble sort, selection sort, dan insertion sort artinya menulis isi array setelah setiap pass, lalu menghitung berapa perbandingan dan berapa pertukaran yang terjadi. Di bawah ini satu array 7 elemen, [29, 10, 14, 37, 13, 5, 41], diurutkan menaik oleh ketiga algoritma. Hasil akhirnya sama, tapi jumlah pertukarannya berbeda jauh: bubble sort 10, selection sort 4, insertion sort 10 pergeseran.

Semua angka di sini sudah dicek dengan menjalankan kodenya.

#Kode yang dipakai untuk tracing

Soal tracing selalu bergantung pada versi kode. Tiga versi berikut adalah yang paling umum di modul Struktur Data dan Algoritma.

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        tukar = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                tukar = True
        if not tukar:
            break

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        if m != i:
            a[i], a[m] = a[m], a[i]

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

Perhatikan tiga hal kecil yang menentukan jawaban. Bubble sort di sini punya flag tukar, jadi bisa berhenti lebih awal. Selection sort hanya menukar kalau m != i. Insertion sort tidak menukar, melainkan menggeser elemen ke kanan lalu menaruh key di celah yang kosong.

#Bubble sort: isi array tiap pass

Bubble sort membandingkan pasangan bersebelahan dari kiri ke kanan dan menukarnya kalau kiri lebih besar. Setelah pass pertama, elemen terbesar pasti sudah di ujung kanan, jadi pass berikutnya memeriksa satu pasangan lebih sedikit.

Rincian pass 1 supaya polanya terlihat:

1. 29 > 10, tukar: [10, 29, 14, 37, 13, 5, 41]
2. 29 > 14, tukar: [10, 14, 29, 37, 13, 5, 41]
3. 29 < 37, tetap
4. 37 > 13, tukar: [10, 14, 29, 13, 37, 5, 41]
5. 37 > 5, tukar: [10, 14, 29, 13, 5, 37, 41]
6. 37 < 41, tetap

Enam perbandingan, empat pertukaran. Pass selanjutnya diringkas dalam tabel.

Angka 5 bergerak ke kiri hanya satu posisi per pass. Karena 5 mulai di indeks 5, ia butuh lima pass untuk sampai ke depan. Inilah kelemahan bubble sort: elemen kecil di ujung kanan merayap sangat lambat.

#Kapan bubble sort berhenti lebih awal?

Bubble sort berhenti ketika satu pass penuh selesai tanpa satu pun pertukaran. Pada array tadi, pass 5 masih menukar (10 dan 5), sehingga pass 6 tetap dijalankan dan baru di situ flag tukar bernilai False. Kebetulan pass 6 juga pass terakhir, jadi flag tidak menghemat apa pun.

Bandingkan dengan array yang hampir terurut, [5, 10, 13, 29, 14, 37, 41]. Hanya 29 dan 14 yang tertukar.

• Pass 1: 6 perbandingan, 1 pertukaran, array menjadi [5, 10, 13, 14, 29, 37, 41].
• Pass 2: 5 perbandingan, 0 pertukaran. Berhenti.

Totalnya 11 perbandingan, bukan 21. Tanpa flag, bubble sort akan tetap menjalankan keenam pass. Jadi kalau soal bertanya "berapa pass yang dijalankan", jawabannya 2 untuk versi dengan flag dan 6 untuk versi tanpa flag. Baca kodenya dulu sebelum menjawab.

#Selection sort: cari minimum, tukar sekali

Selection sort pada pass ke-i mencari elemen terkecil di bagian yang belum terurut, lalu menukarnya ke posisi i. Jumlah perbandingan setiap pass selalu tetap, tidak peduli isi array.

Pada pass 1, angka 5 ditukar dengan 29, sehingga 29 melompat dari indeks 0 ke indeks 5. Pada pass 2 dan pass 6, minimumnya sudah berada di tempat, jadi tidak ada pertukaran.

Selection sort hampir tidak terpengaruh oleh susunan awal. Pada array hampir terurut [5, 10, 13, 29, 14, 37, 41], perbandingannya tetap 21. Pertukarannya saja yang turun menjadi 1. Rumus perbandingannya selalu

$(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}=\frac{7\cdot 6}{2}=21$

Keunggulannya ada di jumlah pertukaran: paling banyak $n-1$, yaitu 6 untuk tujuh elemen. Ini berguna kalau menulis ke memori itu mahal.

#Insertion sort: sisipkan key ke bagian kiri

Insertion sort menganggap bagian kiri array sudah terurut, lalu mengambil satu elemen (key) dan menggesernya ke kiri sampai menemukan tempatnya. Di sini yang dihitung adalah pergeseran, bukan pertukaran.

Cara menghitung perbandingan pada pass 4: key 13 dibandingkan dengan 37 (geser), 29 (geser), 14 (geser), lalu 10. Karena 10 < 13, loop berhenti. Itu empat perbandingan dan tiga pergeseran. Pada pass 5, key 5 lebih kecil dari semua elemen di kirinya, sehingga lima perbandingan dan lima pergeseran, lalu loop berhenti karena j sudah -1 (tidak ada perbandingan keenam).

Ada pola yang bisa kamu pakai untuk mengecek jawaban: jumlah pertukaran bubble sort dan jumlah pergeseran insertion sort selalu sama, yaitu jumlah inversi di array (pasangan yang urutannya terbalik). Array ini punya 10 inversi, dan kedua algoritma memang menghasilkan 10.

#Kenapa insertion sort cepat pada data hampir terurut?

Setiap pass insertion sort berhenti di perbandingan pertama yang gagal. Kalau array sudah hampir terurut, hampir setiap key hanya butuh satu perbandingan.

Pada [5, 10, 13, 29, 14, 37, 41], insertion sort hanya melakukan 7 perbandingan dan 1 pergeseran. Bandingkan hasil ketiga algoritma pada array yang sama:

Untuk array yang sudah terurut penuh, insertion sort butuh tepat $n-1$ perbandingan, jadi kasus terbaiknya $O\left(n\right)$. Kasus terburuknya adalah array terurut terbalik, dengan $\frac{n(n-1)}{2}$ perbandingan, atau $O\left(n^2\right)$. Alasan yang sama membuat insertion sort sering dipakai untuk potongan kecil di dalam algoritma pengurutan yang lebih canggih. Cara menurunkan kelas kompleksitas ini dari kode ada di artikel cara menghitung Big O dari kode.

#Mana yang stabil dan mana yang tidak?

Algoritma pengurutan disebut stabil kalau dua elemen bernilai sama tetap dalam urutan aslinya setelah diurutkan.

Contoh paling mudah untuk soal ujian: [4a, 4b, 1], dengan 4a dan 4b sama-sama bernilai 4.

• Selection sort: pass 1 menemukan minimum 1 di indeks 2 dan menukarnya dengan 4a di indeks 0. Hasilnya [1, 4b, 4a]. Urutan 4a dan 4b terbalik, jadi tidak stabil.
• Bubble sort: 4a dan 4b hanya ditukar kalau a[j] > a[j+1]. Karena 4 > 4 bernilai salah, keduanya tidak pernah ditukar. Hasilnya [1, 4a, 4b]. Stabil.
• Insertion sort: key 4b berhenti di belakang 4a karena syaratnya a[j] > key, bukan >=. Stabil.

Stabilitas bubble sort dan insertion sort bergantung pada tanda pembanding. Kalau > diganti >=, keduanya berubah menjadi tidak stabil, walaupun hasilnya tetap terurut.

#Kesalahan yang sering terjadi saat tracing sorting

1. Menulis array setiap kali ada pertukaran, padahal soal meminta isi array per pass. Satu pass bubble sort bisa berisi beberapa pertukaran, tapi baris jawabannya hanya satu.
2. Menghitung pass bubble sort yang tidak dijalankan. Kalau kodenya punya flag, pass setelah pass tanpa pertukaran tidak ada.
3. Menganggap selection sort selalu menukar. Versi tanpa if m != i memang menukar setiap pass (menukar elemen dengan dirinya sendiri), sehingga totalnya 6, bukan 4. Lihat kodenya.
4. Menyebut pergeseran insertion sort sebagai pertukaran. Satu pergeseran hanya satu penulisan, sedangkan satu pertukaran butuh tiga penulisan dengan variabel sementara. Beberapa soal membedakannya.
5. Lupa bahwa perbandingan terakhir insertion sort yang gagal tetap dihitung. Pass 4 di atas punya empat perbandingan, bukan tiga.
6. Mengurutkan menurun ketika soal meminta menaik, atau sebaliknya. Cek tanda pembandingnya sebelum mulai.

Latihan tracing yang mirip untuk struktur lain: tracing rekursi Python dengan call stack dan traversal pohon biner.

#FAQ

#Berapa jumlah pass maksimum untuk array 7 elemen?

Enam pass untuk ketiga algoritma, yaitu $n-1$. Bubble sort dengan flag bisa berhenti lebih cepat. Selection sort dan insertion sort selalu menjalankan enam pass, walaupun pass insertion sort bisa sangat pendek.

#Apakah selection sort lebih cepat dari bubble sort?

Dari sisi perbandingan, keduanya sama-sama 21 pada kasus terburuk untuk tujuh elemen. Selection sort menang di jumlah pertukaran (4 lawan 10 pada contoh di atas). Pada data hampir terurut, bubble sort dengan flag justru lebih sedikit perbandingannya (11 lawan 21).

#Kenapa jumlah perbandingan selection sort tidak pernah berubah?

Karena untuk menemukan minimum, ia harus memeriksa semua elemen yang belum terurut, apa pun isinya. Tidak ada kondisi berhenti lebih awal di loop dalamnya.

#Apakah insertion sort selalu lebih baik dari bubble sort?

Pada data acak, keduanya $O\left(n^2\right)$, tapi insertion sort biasanya melakukan lebih sedikit perbandingan karena loop dalamnya berhenti begitu tempat key ditemukan. Pada contoh di atas, 14 lawan 21.

#Apa itu inversi dan bagaimana menghitungnya?

Inversi adalah pasangan indeks dengan $a_i>a_j$. Untuk array contoh: 29 membentuk inversi dengan 10, 14, 13, dan 5 (empat), 10 dengan 5 (satu), 14 dengan 13 dan 5 (dua), 37 dengan 13 dan 5 (dua), 13 dengan 5 (satu). Totalnya 10.

#Bagaimana menulis jawaban tracing di lembar ujian?

Tulis tabel dengan kolom pass, isi array setelah pass, dan jumlah perbandingan serta pertukaran. Garis bawahi bagian yang sudah terurut supaya penilai melihat kamu paham posisi akhir tiap elemen. Untuk menyusun langkah algoritmanya dalam bentuk diagram, lihat flowchart dan pseudocode untuk tugas algoritma.