Bubble Sort dan Insertion Sort
Kodekan kedua algoritma pengurutan kuadratik, pahami alasan kompleksitasnya O(n²), dan kenali satu kondisi ketika insertion sort mengungguli merge sort.
Bubble Sort dan Insertion Sort adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Mengapa Mempelajari Pengurutan O(n²)?
Pengurutan gelembung dan pengurutan penyisipan memiliki kompleksitas O(n²) pada kasus terburuk, sehingga tidak praktis untuk masukan berukuran besar. Namun, setiap wawancara algoritme yang serius mengharapkan Anda mampu mengimplementasikan dan menganalisisnya. Keduanya mengajarkan konsep dasar — perbandingan, pertukaran, pengurutan stabil, dan perilaku pada kasus terbaik — yang berlaku pada algoritme yang lebih maju. Pewawancara menggunakannya untuk menguji apakah Anda dapat menalar tentang invarian perulangan dan notasi asimtotik dari prinsip pertama.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Pengurutan Gelembung: Menggelembungkan Nilai Maksimum
Pengurutan gelembung berulang kali memindai larik dan menukar elemen bersebelahan yang urutannya salah. Setelah setiap lintasan penuh, elemen terbesar yang belum terurut ‘menggelembung’ ke posisi akhirnya di bagian akhir. Setelah n-1 lintasan, seluruh larik telah terurut. Namanya berasal dari cara elemen yang lebih besar bergerak ke atas seperti gelembung. Ini merupakan algoritme pengurutan yang paling mudah dijelaskan, tetapi jarang digunakan dalam praktik.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Pengurutan Gelembung dengan Keluar Lebih Awal
Pengurutan gelembung yang dioptimalkan menggunakan penanda swapped: jika satu lintasan bagian dalam yang penuh menghasilkan nol pertukaran, larik sudah terurut dan kita keluar lebih awal. Dengan demikian, kasus terbaiknya adalah O(n) untuk masukan yang sudah terurut — satu-satunya keunggulan nyata pengurutan gelembung. Tanpa penanda ini, algoritme tersebut selalu melakukan perbandingan O(n²). Pengoptimalan keluar lebih awal inilah yang diperiksa pewawancara saat menanyakan peningkatan pada pengurutan gelembung.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passAnalisis Kompleksitas Pengurutan Gelembung
Perulangan luar pengurutan gelembung berjalan sebanyak n-1 kali. Perulangan dalam berjalan sebanyak n-1-i kali pada setiap lintasan: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 perbandingan. Ini menghasilkan O(n²) pada kasus rata-rata dan terburuk. Dengan penanda keluar lebih awal, kasus terbaiknya turun menjadi O(n) untuk masukan yang sudah terurut. Kompleksitas ruangnya adalah O(1) — hanya pertukaran yang memerlukan variabel sementara. Pengurutan gelembung bersifat stabil: elemen yang sama mempertahankan urutan relatifnya karena kita hanya menukar elemen yang benar-benar lebih besar.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Pengurutan Penyisipan: Menyusun Tangan Kartu Terurut
Pengurutan penyisipan meniru cara menyusun tangan kartu: ambil kartu (elemen) berikutnya dan sisipkan ke posisi yang tepat di antara kartu yang sudah terurut di sebelah kiri. Invariannya adalah arr[0:i] selalu terurut. Untuk setiap elemen baru, geser elemen yang lebih besar ke kanan untuk menyediakan tempat. Algoritme yang dilakukan di tempat dan stabil ini memiliki kasus terburuk O(n²), tetapi kasus terbaik O(n) untuk data yang hampir terurut.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Pengurutan Penyisipan Langkah demi Langkah
Lacak pengurutan penyisipan pada [3, 1, 4, 2]: i=1, key=1, geser 3 ke kanan → [1, 3, 4, 2]. i=2, key=4, tidak ada pergeseran → tetap. i=3, key=2, geser 4 lalu 3 ke kanan → [1, 2, 3, 4]. Setiap elemen dibandingkan dengan elemen di sebelah kirinya sampai kita menemukan tempat yang tepat. Perulangan dalam while melakukan pergeseran menggunakan penugasan (lebih cepat daripada pertukaran karena setiap pergeseran memerlukan satu penugasan, sedangkan pertukaran memerlukan tiga).
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Pengurutan Penyisipan pada Data yang Hampir Terurut
Keunggulan utama pengurutan penyisipan adalah kompleksitasnya, yaitu O(n + inversi). Inversi adalah pasangan (i,j) dengan i < j tetapi arr[i] > arr[j]. Untuk larik yang hampir terurut dan hanya memiliki sedikit inversi, pengurutan penyisipan sangat cepat — terkadang lebih cepat daripada pengurutan gabung dalam praktik karena kesederhanaannya dan pola aksesnya yang ramah cache. Timsort Python menggunakan pengurutan penyisipan pada sublarik kecil karena alasan ini.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Stabilitas dalam Pengurutan
Algoritme pengurutan bersifat stabil jika elemen yang sama mempertahankan urutan relatif aslinya setelah diurutkan. Pengurutan gelembung dan pengurutan penyisipan sama-sama stabil — keduanya tidak pernah menukar elemen yang sama. Stabilitas penting saat Anda mengurutkan berdasarkan beberapa kunci secara berurutan: urutkan berdasarkan kunci sekunder terlebih dahulu (secara stabil), lalu urutkan berdasarkan kunci utama (secara stabil) agar urutan kunci sekunder di antara nilai yang sama tetap terjaga. Pengurutan gabung juga stabil; pengurutan heap dan pengurutan cepat umumnya tidak stabil.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stablePengurutan Penyisipan sebagai Pencarian Biner
Perulangan dalam pengurutan penyisipan sekaligus menemukan posisi yang tepat dan menggeser elemen. Anda dapat menggunakan pencarian biner untuk menemukan posisi dalam O(log i) perbandingan, tetapi pergeseran tetap memerlukan waktu O(i) — sehingga kompleksitas keseluruhannya tetap O(n²). Pengoptimalan ini mengurangi jumlah perbandingan (berguna untuk fungsi perbandingan yang mahal), tetapi tidak mengurangi jumlah total operasi. ‘Pengurutan penyisipan biner’ ini digunakan dalam Timsort untuk ukuran potongan kecil.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Gelembung dan Penyisipan: Kapan Menggunakan Masing-Masing
Dalam wawancara, sampaikan perbandingan ini dengan yakin: pengurutan penyisipan secara mutlak lebih baik daripada pengurutan gelembung — keduanya memiliki kasus terburuk O(n²) dan ruang O(1), tetapi pengurutan penyisipan melakukan lebih sedikit penulisan (O(n+k) untuk k inversi dibandingkan O(n²) untuk pengurutan gelembung), lebih ramah cache, dan merupakan pilihan praktis untuk n yang kecil (Timsort menggunakannya). Satu-satunya keunggulan nyata pengurutan gelembung adalah kesederhanaannya untuk pembelajaran. Dalam produksi, selalu gunakan sort bawaan bahasa.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Menghitung Inversi sebagai Metrik
Jumlah inversi dalam sebuah larik sama dengan jumlah pasangan (i,j) dengan i < j tetapi arr[i] > arr[j]. Pengurutan penyisipan melakukan tepat sebanyak pergeseran yang sama dengan jumlah inversi — sebuah wawasan yang berguna. Penghitungan inversi secara efisien (O(n log n)) memerlukan pengurutan gabung yang dimodifikasi. Pewawancara terkadang menanyakan, ‘Sejauh mana algoritme Anda memperhitungkan inversi?’ sebagai pertanyaan lanjutan dalam diskusi pengurutan.
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedCek Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: pengurutan gelembung melakukan n-1 lintasan, masing-masing menggelembungkan nilai maksimum saat ini ke posisi akhirnya, dengan kasus terburuk O(n²) tetapi kasus terbaik O(n) jika menggunakan penanda keluar lebih awal, pengurutan penyisipan menggeser elemen ke kanan untuk menyisipkan key saat ini ke posisi terurut yang tepat, berjalan dalam waktu O(n + inversi) sehingga optimal untuk data yang hampir terurut, dan kedua algoritme bersifat stabil, menggunakan ruang O(1), serta memiliki kasus terburuk O(n²) — tetapi pengurutan penyisipan selalu lebih disarankan daripada pengurutan gelembung dalam semua situasi praktis. Selanjutnya kita akan mengimplementasikan pengurutan gabung dari awal.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Bubble Sort dan Insertion Sort” gratis?
Ya — teks lengkap “Bubble Sort dan Insertion Sort” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Bubble Sort dan Insertion Sort”?
Kodekan kedua algoritma pengurutan kuadratik, pahami alasan kompleksitasnya O(n²), dan kenali satu kondisi ketika insertion sort mengungguli merge sort. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Bubble Sort dan Insertion Sort” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Bubble Sort dan Insertion Sort
- Merge Sort: Bagi, Urutkan, Gabungkan
- Quick Sort dan Pemilihan Pivot
- Pengurutan Tanpa Perbandingan dan sort() Python