Cara kerja
Mengisih bermakna menyusun item berturutan — dari terkecil ke terbesar, A hingga Z. Semua algoritma di bawah menyelesaikan masalah yang sama; bezanya hanya strategi, dan strategilah yang anda saksikan. Pilih satu algoritma (atau mod perlumbaan untuk keenam-enamnya sekali gus), pilih input, lalu tekan main. Bar menyala semasa enjin bekerja: kuning menandai perbandingan, merah menandai pergerakan atau pertukaran, ungu menandai pivot, dan hijau menandai kedudukan yang selesai.
Kawalannya mirip pemain video kerana enjinnya memang begitu: main dan jeda dengan bar ruang, selangkah demi selangkah dengan anak panah kanan, mula semula dengan R, senarai baharu dengan N, rawak dengan S, dan kelajuan 0,25× hingga 8×. Panel kod menyerlahkan setiap baris pseudokod semasa dilaksanakan, supaya animasi dan program berjalan segerak. Cuba perlumbaan yang sama dua kali: sekali dengan senarai terbalik, sekali hampir tertib, dan saksikan Insertion Sort melompat dari barisan belakang ke hadapan.
Keenam-enam algoritma
Tiga daripadanya kaedah kuadratik yang ringkas — mudah ditulis, menyeksakan dalam skala besar. Tiga lagi kaedah cekap yang mencapai O(n log n) dengan bahagi-dan-takluk atau struktur data yang bijak. Setiap contoh di bawah ialah Python lengkap yang boleh dijalankan, bekerja pada senarai biasa.
Bubble Sort — pertukaran jiran
Susuri senarai sambil membandingkan jiran dan menukar pasangan yang tidak berturutan. Setiap lintasan membuat item terbesar yang belum tertib “terapung” ke tempat akhirnya, supaya lintasan berikut boleh satu langkah lebih pendek. Jika satu lintasan penuh tidak menukar apa-apa, senarai sudah tertib dan algoritma berhenti awal — satu-satunya sifat penebusnya, yang memberi O(n) untuk input yang sudah tertib.
def bubble_sort(a):
n = len(a)
for end in range(n - 1, 0, -1):
swapped = False
for i in range(end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
return aSelection Sort — pilih yang terkecil, ulangi
Bahagi senarai kepada depan yang tertib dan baki yang belum. Setiap langkah, imbas seluruh baki untuk mencari minimumnya lalu tukar ke tempatnya. Ia sentiasa melakukan bilangan perbandingan yang sama — sekitar n²/2 — seberapa pun tertibnya input; kerana itu kes terbaik, purata dan terburuk semuanya O(n²). Kelebihannya ialah melakukan paling banyak n pertukaran, dahulu berguna ketika menukar itu mahal.
def selection_sort(a):
n = len(a)
for i in range(n):
m = i
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return aInsertion Sort — cara pemain kad
Seperti orang mengisih kad di tangan: ambil item berikutnya lalu luncurkan ke kiri melepasi semua yang lebih besar hingga muat. Pada data hampir tertib hampir tiada yang bergerak, jadi berjalan O(n) — terpantas di bilik untuk kes itu, dan sebab pengisihan hibrid sebenar memakainya untuk subsenarai kecil. Pada data terbalik setiap item menempuh jarak penuh: kes terburuk O(n²). Ia stabil dan tidak memakai memori tambahan.
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
return aMerge Sort — bahagi, takluk, gabung
Belah senarai menjadi dua, isih setiap belahan dengan cara yang sama (rekursi berhenti pada item tunggal, yang sudah tertib menurut takrifan), lalu gabungkan kedua-dua belahan tertib dengan sentiasa mengambil item depan yang lebih kecil. Belahan sentiasa seimbang, jadi setiap tahap berbiaya O(n) dan ada log n tahap: O(n log n) terjamin, dalam semua kes. Harganya O(n) memori tambahan untuk menggabung, dan ia stabil — item yang sama tidak pernah saling bersilang.
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]Quick Sort — sekatan dengan pivot
Pilih pivot, lalu sekat: semua yang lebih kecil ke kiri, semua yang lebih besar ke kanan. Isih setiap sisi dengan cara yang sama. Bila pivot jatuh berhampiran tengah, rekursi sedalam log n tahap dan jumlahnya O(n log n) dengan pemalar mungil dan hanya O(log n) memori tambahan untuk rekursi — umumnya terpantas dalam amalan. Bila jatuh di hujung, satu sisi memuat hampir semuanya dan ia merosot ke O(n²). Simulator ini memilih pivot denganmedian-daripada-tiga (item pertama, tengah dan terakhir), jadi kes buruk jarang pada data sebenar. Contoh Python di bawah hanya menggunakan item terakhir sebagai pivot supaya ringkas.
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
p, i = a[hi], lo
for j in range(lo, hi):
if a[j] < p:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
quick_sort(a, lo, i - 1)
quick_sort(a, i + 1, hi)
return aHeap Sort — barisan keutamaan yang menyamar
Ubah senarai menjadi max-heap: pokok binari yang dipadatkan ke dalam tatasusunan di mana setiap induk lebih besar daripada anaknya, jadi maksimum ada di kedudukan sifar. Ambil maksimum berulang kali, tukar ke hujung, susutkan heap satu, dan pulihkan sifatnya dengan menurunkan puncak baharu. O(n log n) terjamin dengan O(1) memori tambahan — tetapi pola capaian yang melompat-lompat tidak disukai cache pemproses, jadi biasanya kalah kepada Quick dan Merge Sort di jam randik, meski seri di atas kertas.
def heap_sort(a):
def sift(lo, n, i):
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < n and a[lo + l] > a[lo + m]:
m = l
if r < n and a[lo + r] > a[lo + m]:
m = r
if m == i:
return
a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
i = m
n = len(a)
for i in range(n // 2 - 1, -1, -1):
sift(0, n, i)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift(0, end, 0)
return aMembaca jadual
Big-O menggambarkan pertumbuhan, bukan jam randik: pemalar dan perkakasan sengaja diabaikan supayabentuk skalanya terlihat. Jadual di bawah ialah acuan baku (Cormen dkk.,Introduction to Algorithms; Kamus Algoritma dan Struktur Data NIST). “Stabil” bermakna item yang sama mengekalkan tertib asal.
| Algoritma | Terbaik | Purata | Terburuk | Memori tambahan | Stabil |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Tidak |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ya |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Tidak |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Tidak |
Cuba dalam simulator: lombakan keenam-enamnya dengan senarai terbalik kemudian hampir tertib. Tertib penamat berbalik — Insertion Sort melompat dari barisan belakang ke hadapan — dan tiada formula yang mengajarnya seperti menyaksikannya.
Tiga kesilapan lazim
“Quick Sort sentiasa yang paling pantas.” Secara purata Quick Sort antara yang terpantas, tetapi Quick Sort yang ringkas mempunyai kes terburuk O(n²), contohnya apabila pangsi sentiasa jatuh di satu hujung senarai. Merge Sort dan Heap Sort kekal O(n log n) walau apa pun inputnya.
“Kaedah kuadratik yang ringkas tidak berguna.” Insertion Sort digunakan secara meluas untuk senarai kecil dan sangat baik pada senarai yang hampir tersusun. Rutin isihan yang digunakan dalam amalan biasanya hibrid dan bertukar kepada Insertion Sort untuk bahagian kecil.
“Isihan stabil ialah isihan yang tidak pernah gagal.” Kestabilan mempunyai maksud yang tepat: item dengan kunci yang sama mengekalkan tertib yang dimilikinya sebelum diisih. Merge Sort dan Insertion Sort adalah stabil; Quick Sort dan Heap Sort, dalam bentuk biasanya, tidak.
Soalan pengunjung
Algoritma pengisihan mana yang patut diguna dalam kod sebenar?
Hampir selalu pengisihan natif bahasa: sorted() Python, Array.sort() JavaScript, atau Arrays.sort() Java untuk objek. Semuanya hibrid kejuruteraan (Python dan Java guna Timsort) berwaktu O(n log n), stabil, dan teruji jutaan pengguna. Keenam-enam algoritma di halaman ini mengajar idea di sebalik perkakas itu, bukan menggantikannya.
Jika Bubble Sort perlahan, mengapa masih diajar?
Kerana itu idea pengisihan paling ringkas: bandingkan jiran, tukar jika tidak bertertib, ulangi. Melihatnya terseksa di samping Merge Sort dalam mod perlumbaan mengajar lebih banyak tentang pertumbuhan O(n²) daripada sebarang formula. Berhenti awal juga menunjukkan algoritma yang sama boleh O(n) untuk input yang sudah tertib dan O(n²) secara umum.
Apakah maksud pengisihan yang stabil?
Pengisihan stabil mengekalkan item yang sama pada tertib relatif asal. Ini penting ketika mengisih dengan lebih daripada satu kunci: isih kelas mengikut nama kemudian markah dengan algoritma stabil, dan murid bermarkah sama kekal tersusun abjad. Merge, Insertion dan Bubble Sort stabil; Selection, Quick dan Heap Sort, sebagaimana biasa dilaksanakan, tidak.
Mengapa Quick Sort tidak selalu terpantas walaupun purata O(n log n)?
Kerana kes terburuknya O(n²): dengan pivot malang, setiap sekatan hanya mengasingkan satu item. Pelaksanaan yang baik mengelakkannya dengan pivot median-daripada-tiga (seperti dalam simulator ini) atau rawak. Merge Sort menjamin O(n log n) tetapi mengguna O(n) memori tambahan; Heap Sort menjamin O(n log n) di tempat, tetapi melompat-lompat dalam memori, yang tidak disukai cache moden.
Adakah simulator benar-benar melaksanakan algoritma, atau hanya animasi?
Benar-benar melaksanakannya. Setiap algoritma menjalankan logik tulennya dan memancarkan peristiwa langkah — banding, tukar, tulis-semula, pivot, gabung, heapify — yang dimainkan semula oleh carta animasi. Dalam mod perlumbaan keenam-enamnya memakai input yang sama bersebelahan, jadi perbandingannya adil. Mod perkataan mengisih teks tanpa membeza aksen mahupun huruf besar.
Sebenarnya apakah yang dikira oleh tatatanda Big-O?
Bagaimana bilangan langkah asas tumbuh mengikut input, dengan mengabaikan faktor malar. O(n²) bermakna menggandakan input hampir melipatgandakan kerja; O(n log n) bermakna menggandakan hanya sedikit lebih daripada menggandakan. Pada n = 1,000,000, itulah beza antara sekitar satu trilion operasi dan dua puluh juta — hitungan minit atau jam berbanding sepersekian saat.
Sumber dan bacaan lanjutan
- Introduction to Algorithms — MIT Press (Cormen et al.)
- Sorting algorithm — Wikipedia
- Dictionary of Algorithms and Data Structures — NIST
- Algorithms course — Khan Academy
Sitasi pameran ini
Eurekarium. (2026). Makmal Pengisihan. https://eurekarium.com/ms/computing/sorting-lab/
Kemas kini terakhir: