Algoritma pengurutan
| English | Bahasa Indonesia |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | bubble sort |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | insertion sort |
| in place/ɪn pleɪs/ | in place |
| 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
membandingkan elemen berdekatan, menukar jika perlu
Lakukan langkah-langkah bubble sort: setiap putaran mengangkat nilai terbesar ke posisi akhir.
Bubble sort bekerja dengan cara:
Setiap putaran menukar pasangan berdekatan, "menggelembungkan" elemen terbesar ke posisi akhir.
Kompleksitas waktu rata-rata/kasus terburuk dari bubble sort adalah:
Dua loop bersarang atas n elemen menghasilkan O(n²); kasus terbaik (sudah terurut) adalah O(n) dengan keluaran dini.
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 membangun hasil terurut dengan cara:
Algoritma ini mengembangkan prefix terurut di sebelah kiri, menggeser elemen yang lebih besar ke kanan untuk menempatkan setiap kunci.
Bagaimana insertion sort menempatkan setiap elemen baru?
Menahan kunci sementara dan menggeserlah yang membedakannya dari menukar berdekatan yang berulang pada bubble sort.
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.
Setelah putaran pertama bubble sort pada 5, 3, 8, 1, bagaimana susunan array-nya? Tulis empat angka dipisahkan oleh koma.
5 dan 3 bertukar, 5 dan 8 tidak bertukar, 8 dan 1 bertukar. Nilai terbesar telah mencapai posisi akhir, jadi putaran berikutnya bisa satu perbandingan lebih pendek.
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.
Cocokkan setiap ide pengurutan dengan maknanya.
Bubble sort menukar tetangga, insertion sort mengembangkan prefix terurut; keduanya memiliki kasus terburuk O(n²); stabilitas berkaitan dengan urutan kunci yang sama.
Insertion sort berjalan mendekati O(n) pada array kecil atau hampir terurut, karena sedikit elemen yang perlu digeser.
Pada data yang hampir terurut, setiap item baru sudah hampir berada di tempatnya — itulah sebabnya insertion sort mengalahkan pengurutan yang lebih rumit pada input kecil.
Manakah yang benar mengenai bubble sort dan insertion sort? Pilih semua yang berlaku.
Pada daftar tak terurut yang besar, pengurutan O(n log n) menang telak. Menyatakan hal itu adalah jawaban yang tepat, bukan memilih yang paling buruk di antara keduanya.
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.
Daftar terurut dari 10,000 rekaman memperoleh 5 rekaman baru di bagian akhir. Urutan mana yang cocok untuk mengurutkannya kembali?
Hampir terurut adalah kasus terbaik untuk insertion sort, mendekati O(n). Perpustakaan nyata beralih ke algoritma ini karena alasan tersebut.
Pasangkan setiap pengurutan dengan apa yang dicapai dalam satu kali perulangan.
Perbedaan itulah yang sebenarnya diuji oleh soal pelacakan (trace question). Flag bubble-sort juga memungkinkannya berhenti lebih awal pada data hampir terurut, yang memang ditangani dengan baik oleh insertion sort.
⟦⟧ Nilai yang sering 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