Sorting algorithms
Diperkenalkan| English | Makna |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | pengurutan gelembung |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | penyisipan |
| in place/ɪn pleɪs/ | di tempat |
| stable/ˈsteɪbl/ | stabil |
Urutan yang sengaja lambat
- Setiap perpustakaan serius menggunakan algoritma pengurutan yang tidak diminta dalam ujian. Bubble sort dan insertion sort keduanya $O(n^2)$, dan keduanya dikalahkan oleh algoritma pengurutan yang memadai apa pun pada daftar besar.
- Mereka tetap ada dalam silabus, dan karena alasan yang baik: mereka cukup pendek untuk dilacak secara manual, dan melacak salah satunya adalah cara Anda mempelajari apa sebenarnya yang dilakukan algoritma pengurutan terhadap sebuah array.
- Ada juga kasus nyata untuk insertion sort. Pada daftar yang kecil, atau hampir terurut, ini benar-benar yang tercepat, dan perpustakaan nyata beralih ke algoritma ini untuk kasus-kasus tersebut.
- Pelajaran ini adalah bubble sort dan insertion sort: algoritmanya, perilakunya, dan di mana masing-masing menang.
Urut gelembung
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
swap A[i], A[i + 1]
swapped ← TRUE
ENDIF
NEXT i
IF NOT swapped THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
- Setiap lintasan membandingkan pasangan bersebelahan dan menukar apa pun yang tidak sesuai urutan, sehingga nilai terbesar yang tersisa "menggembung" ke akhir.
- Setelah lintasan $k$, $k$ elemen terakhir sudah final, itulah sebabnya loop dalam berhenti di $n - \text{pass}$.
- Flag
swappedmemungkinkan penghentian dini: jika seluruh lintasan tidak melakukan penukaran, daftar sudah terurut.
Insertion sort
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j] // shift right
j ← j - 1
ENDWHILE
A[j + 1] ← key // drop it in
NEXT i
- Ini membangun bagian terurut di bagian depan, bertambah satu setiap kali. Setiap elemen baru disimpan sementara sebagai
key, elemen lebih besar digeser ke kanan untuk membuka celah, dan kunci dimasukkan. - Inilah bagaimana sebagian besar orang mengurutkan tumpukan kartu remi, yang merupakan analogi yang diharapkan dalam ujian.

Kiri sudah terurut, kanan belum tersentuh, dan batas bergerak ke kanan
Algoritma pengurutan
compare adjacent, swap if needed
Step through a bubble sort: each pass floats the largest value to the end.
Bubble sort works by:
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Each pass swaps adjacent pairs, "bubbling" the largest element to the end.
The average/worst-case time complexity of bubble sort is:
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit.
Contoh dikerjakan: jejak satu lintasan
- Jejakkan lintasan pertama bubble sort pada 5, 3, 8, 1.
- Bandingkan 5 dan 3: tidak sesuai urutan, tukar, menghasilkan 3, 5, 8, 1. Bandingkan 5 dan 8: sesuai urutan, tidak ditukar. Bandingkan 8 dan 1: tukar, menghasilkan 3, 5, 1, 8.
- Setelah satu lintasan, nilai terbesar, 8, berada di posisi akhirnya, dan satu perbandingan tambahan per lintasan dapat dilewati mulai sekarang.
- Sekarang jejakkan langkah ketiga insertion sort pada 3, 5, 8, 1. Kuncinya adalah 1. Geser 8, 5, dan 3 masing-masing satu tempat ke kanan, lalu letakkan 1 di depan: 1, 3, 5, 8. Tampilkan array setelah setiap langkah; di situlah nilainya diperoleh.
Insertion sort builds the sorted result by:
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place.
How does insertion sort place each new element?
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps.
Kinerja
| bubble | insertion | |
|---|---|---|
| kasus terbaik | $O(n)$, satu lintasan tanpa penukaran | $O(n)$, sudah terurut, tanpa geseran |
| rata-rata dan terburuk | $O(n^2)$ | $O(n^2)$ |
| memori tambahan | $O(1)$, in place | $O(1)$, in place |
| stabil | ya | ya, stabil |
- In place berarti hanya memerlukan jumlah memori ekstra konstan, mengurutkan di dalam array itu sendiri. Stabil berarti dua nilai yang sama mempertahankan urutan relatif aslinya, yang penting ketika daftar sudah diurutkan berdasarkan bidang lain.
- Keduanya mencapai $O(n)$ pada data yang sudah terurut, tetapi hanya jika bubble sort memiliki flag
swapped. Tanpa itu, ia selalu melakukan semua lintasan.
After the first pass of a bubble sort on 5, 3, 8, 1, what is the array? Write the four numbers separated by commas.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
5 and 3 swap, 5 and 8 do not, 8 and 1 swap. The largest value has reached the end, so the next pass can be one comparison shorter.
Contoh dikerjakan: algoritma pengurutan mana, dan mengapa
- Daftar 200,000 rekaman harus diurutkan dari awal. Tidak: keduanya $O(n^2)$, jadi penggabungan atau quick sort pada $O(n \log n)$ diperlukan. Sebutkan itu daripada memilih yang paling buruk.
- Daftar terurut 10,000 mendapatkan 5 rekaman baru di akhir dan harus diurutkan lagi. Sortir sisip: data hampir terurut, sehingga setiap kunci baru hanya bergeser sedikit dan mendekati $O(n)$.
- Contoh pengajaran harus ditelusuri secara manual di atas kertas. Bubble sort: ini paling mudah diikuti, yang merupakan penggunaan utamanya yang tersisa.
- Justifikasikan dari keadaan data dan ukurannya, bukan dari preferensi umum.
Match each sorting idea to what it means.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs.
Which are true of both bubble sort and insertion sort? Select semua that apply.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
On a large unsorted list an O(n log n) sort wins decisively. Saying so is the right answer, not choosing the least bad of the two.
Mengapa satu lintasan bukan keseluruhan cerita
- Kedua algoritma pengurutan melakukan lintasan berulang, dan ujian membedakan keduanya berdasarkan apa yang dicapai dalam satu lintasan dan kapan mereka berhenti.
- Lintasan bubble sort membandingkan pasangan bersebelahan dan menukarnya, sehingga satu lintasan membawa item terbesar yang tersisa ke posisi akhirnya. Seluruh pengurutan terdiri dari $n - 1$ lintasan.
- Lintasan insertion sort mengambil item selanjutnya dan memindahkannya kembali ke bagian yang sudah terurut, sehingga setelah $k$ lintasan, $k$ item pertama terurut satu sama lain tetapi belum dalam posisi final.
- Bubble sort dapat ditingkatkan dengan flag: jika suatu lintasan tidak melakukan penukaran, daftar sudah terurut dan algoritma berhenti. Pada data hampir terurut, ini mengubahnya menjadi satu lintasan.
- Tanpa flag, keduanya $n^2$ dalam kasus terburuk, itulah sebabnya keduanya pilihan buruk untuk file besar dan mengapa ujian menanyakan tentang yang kecil.
A sorted list of 10,000 records gains 5 new records at the end. Which sort suits re-sorting it?
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason.
Match each sort to what one pass achieves.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
That difference is what a trace question is really testing. A bubble-sort flag also lets it stop early on nearly-sorted data, which insertion sort handles well anyway.
Nilai yang mudah terlewat
- Bubble sort membandingkan pasangan bersebelahan. Jawaban yang membandingkan elemen dengan semua elemen lainnya sedang mendeskripsikan algoritma yang berbeda.
- Loop dalam memendekkan setiap kali putaran, karena bagian akhir array sudah final. Jelaskan mengapa.
- Sortasi sisip menggeser elemen ke kanan untuk membuka celah; tidak menukar berulang-ulang. Perbedaan inilah inti dari algoritma ini.
- Keduanya $O(n^2)$ rata-rata dan terburuk, dan $O(n)$ terbaik. Berikan kasus dengan urutan tersebut.
Anda telah memahaminya
- bubble sort: putaran berulang membandingkan pasangan bersebelahan dan menukar, elemen terbesar 'menggelembung' ke akhir, loop dalam memendekkan setiap putaran, dengan flag
swappeduntuk keluar lebih awal - insertion sort: tumbuhkan bagian yang sudah terurut di depan, pegang setiap kunci di samping, geser elemen yang lebih besar ke kanan dan masukkan kunci ke dalam celah
- keduanya $O(n^2)$ rata-rata dan terburuk, $O(n)$ terbaik, in place dan stabil
- insertion sort benar-benar menang pada daftar kecil atau hampir terurut; untuk daftar acak yang besar, keduanya bukan jawaban yang tepat