Pengurutan Tanpa Perbandingan dan sort() Python
Pelajari counting sort dan radix sort untuk array bilangan bulat, serta pahami cara kerja Timsort Python pada pemanggilan sort bawaan.
Pengurutan Tanpa Perbandingan dan sort() Python adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 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.
Batas Bawah O(n log n) untuk Perbandingan
Algoritme pengurutan apa pun yang menentukan urutan hanya melalui perbandingan elemen memerlukan setidaknya Ω(n log n) perbandingan dalam kasus terburuk. Hal ini dibuktikan melalui argumen pohon keputusan: mengurutkan n elemen memerlukan pembedaan antara n! kemungkinan urutan. Pohon keputusan biner (setiap simpulnya adalah perbandingan) memerlukan setidaknya log₂(n!) ≈ n log₂(n) tingkat. Untuk melewati batas ini, kita memerlukan informasi tambahan tentang elemen-elemen tersebut — misalnya, bahwa elemen itu merupakan bilangan bulat dengan rentang terbatas.
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingPengurutan dengan Penghitungan: Mengurutkan berdasarkan Frekuensi
Pengurutan dengan penghitungan bekerja dengan menghitung frekuensi setiap nilai, lalu menyusun kembali larik terurut dari hitungan tersebut. Algoritme ini memerlukan pengetahuan tentang rentang nilai [0, k) sebelumnya. Kompleksitas waktu: O(n + k); kompleksitas ruang: O(k). Untuk k yang kecil dibandingkan n (misalnya, mengurutkan usia 0–120 atau satu digit), pengurutan dengan penghitungan mengungguli semua algoritme pengurutan berbasis perbandingan. Untuk k yang besar, biaya ruang O(k) membuatnya tidak praktis.
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)Pengurutan Berbasis Penghitungan yang Stabil dengan Hitungan Kumulatif
Untuk pengurutan berbasis penghitungan yang stabil (penting saat mengurutkan objek berdasarkan kunci), hitung jumlah kumulatif sehingga cum[v] memberikan posisi awal nilai v pada keluaran. Pindai larik masukan dari kanan ke kiri, tempatkan setiap elemen pada posisi cum[key] - 1, lalu kurangi posisi tersebut. Dengan demikian, pengurutan menjadi stabil — elemen dengan kunci yang sama tetap berada dalam urutan relatif seperti semula.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Pengurutan Berdasarkan Digit: Mengurutkan Digit Satu per Satu
Pengurutan radix mengurutkan bilangan bulat digit demi digit, mulai dari digit yang paling tidak signifikan (LSD) hingga yang paling signifikan (MSD), menggunakan pengurutan stabil (seperti pengurutan berbasis penghitungan) pada setiap posisi digit. Setelah d lintasan (satu untuk setiap digit), larik telah terurut sepenuhnya. Kompleksitas waktu: O(d × (n + k)), dengan d = jumlah digit dan k = basis (biasanya 10). Untuk n bilangan bulat yang dibatasi oleh W, d = log_k(W), sehingga totalnya O(n log_k(W)).
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Pengurutan Berbasis Wadah: Membagi ke Dalam Wadah
Pengurutan berbasis wadah membagi elemen ke dalam sejumlah wadah tetap berdasarkan rentang nilai, mengurutkan setiap wadah (dengan pengurutan penyisipan untuk wadah kecil), lalu menggabungkannya. Untuk data yang terdistribusi merata dalam [0, 1), n wadah menghasilkan waktu rata-rata O(n). Waktu: O(n + k) secara rata-rata, O(n²) pada kasus terburuk (semua elemen berada dalam satu wadah). Metode ini paling berguna ketika distribusi data diketahui dan kira-kira merata.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listTimsort Python di Balik Layar
sorted() dan list.sort() Python menggunakan Timsort, yang dirancang oleh Tim Peters pada 2002. Timsort merupakan gabungan pengurutan gabung dan pengurutan penyisipan. Timsort memindai 'rangkaian alami' (subsekuens yang sudah terurut) dan menggunakan pengurutan penyisipan untuk membentuk rangkaian hingga 64 elemen. Setelah itu, rangkaian digabungkan menggunakan pengurutan gabung dengan beberapa pengoptimalan: lompatan (melewati banyak elemen sekaligus ketika salah satu rangkaian lebih dominan) dan penumpukan panjang rangkaian.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')sort() Python vs sorted(): Perbedaan Utama
list.sort() mengurutkan di tempat, mengembalikan None, dan hanya bekerja pada list. sorted(iterable) bekerja pada iterable apa pun (tuple, generator, dict) dan mengembalikan list baru. Keduanya menerima parameter key dan reverse. Kesalahan yang umum terjadi: menetapkan hasil pengembalian lst.sort() ke sebuah variabel, lalu bertanya-tanya mengapa nilainya None. Selalu gunakan sorted() ketika Anda memerlukan versi yang sudah terurut dan ingin mempertahankan versi asli.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Kunci Pengurutan Khusus dalam Wawancara
sort Python menerima fungsi key yang dievaluasi satu kali untuk setiap elemen (berbeda dengan pembanding C yang dipanggil untuk setiap pasangan). Kunci pengurutan yang umum dalam wawancara: len untuk panjang string, lambda x: -x untuk urutan menurun, lambda x: (x[1], x[0]) untuk pengurutan berdasarkan banyak kunci, dan str.lower untuk pengurutan tanpa membedakan huruf besar-kecil. sort Python dijamin stabil, sehingga pengurutan berdasarkan banyak kunci bekerja dengan benar.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]Kapan Menggunakan Setiap Pengurutan dalam Wawancara
Pilih pengurutan yang tepat sesuai konteks:
- Gunakan sorted()/list.sort() Python: pilihan bawaan untuk semua soal wawancara — Timsort optimal
- Pengurutan berbasis penghitungan: ketika nilainya berupa bilangan bulat kecil dengan rentang terbatas (0 hingga k, k kecil)
- Pengurutan radix: ketika mengurutkan banyak bilangan bulat dengan lebar bit atau jumlah digit yang diketahui
- Pengurutan berbasis wadah: ketika data berupa pecahan yang terdistribusi merata dalam rentang yang diketahui
- Implementasikan pengurutan gabung: ketika diminta menulis pengurutan stabil O(n log n) dari awal
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Pengurutan Tanpa Pengurutan: K Teratas dengan Tumpukan
Banyak soal wawancara meminta hasil yang menyerupai pengurutan tanpa mengharuskan pengurutan lengkap. Untuk menemukan k elemen teratas: tumpukan minimum berukuran k berjalan dalam O(n log k) — lebih cepat daripada O(n log n) ketika k << n. Untuk menemukan elemen terbesar ke-k: quickselect berjalan dalam O(n) secara rata-rata. Untuk menemukan median: pendekatan dua tumpukan berjalan dalam O(log n) untuk setiap penyisipan. Pendekatan pengurutan parsial ini penting untuk diketahui sebagai alternatif yang lebih cepat daripada pengurutan lengkap.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
if lo >= hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]; i = lo - 1
for j in range(lo, hi):
if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Stabilitas Pengurutan dalam Pengurutan Banyak Kunci
Stabilitas memungkinkan pengurutan berdasarkan banyak kunci dilakukan dengan benar: urutkan berdasarkan kunci sekunder terlebih dahulu (secara stabil), lalu berdasarkan kunci utama (secara stabil). Urutan sekunder dipertahankan untuk nilai yang sama pada kunci utama. Teknik ini digunakan dalam basis data (ORDER BY col1, col2) dan dalam pengurutan radix (setiap lintasan digit harus stabil agar algoritme secara keseluruhan benar). sort Python selalu stabil, sehingga pola ini dapat diandalkan.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: pengurutan berbasis perbandingan memiliki batas bawah O(n log n) — untuk melampaui batas ini diperlukan informasi nonperbandingan seperti bilangan bulat dengan rentang terbatas, pengurutan berbasis penghitungan mencapai O(n + k) dengan menghitung frekuensi, pengurutan radix memproses digit dengan total O(d × (n + k)), dan pengurutan berbasis wadah memanfaatkan distribusi merata untuk mencapai O(n) secara rata-rata, serta Timsort Python adalah pilihan praktis bawaan — stabil, memiliki kasus terburuk O(n log n), kasus terbaik O(n), dan lebih cepat daripada alternatif yang ditulis secara manual untuk data nyata. Selanjutnya kita akan menguasai pencarian biner klasik.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pengurutan Tanpa Perbandingan dan sort() Python” gratis?
Ya — teks lengkap “Pengurutan Tanpa Perbandingan dan sort() Python” 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 “Pengurutan Tanpa Perbandingan dan sort() Python”?
Pelajari counting sort dan radix sort untuk array bilangan bulat, serta pahami cara kerja Timsort Python pada pemanggilan sort bawaan. 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 4 dari 4.
Berapa lama pelajaran “Pengurutan Tanpa Perbandingan dan sort() Python” 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