Satu pusingan isihan ialah satu sapuan melalui senarai yang membandingkan item jiran dan menukarnya apabila urutannya salah. Soalan mungkin meminta anda menunjukkan senarai selepas satu pusingan, mengira pertukaran, atau menerangkan fungsi satu baris kod.
Pelajaran ini sebahagian daripada carian, isihan dan fail. Semak sukatan Cambridge untuk tahun peperiksaan anda bagi mengetahui setakat mana algoritma isihan dijangka. Kemahiran menjejak itu sendiri boleh dibawa ke mana-mana, dan ia dibina atas penjejakan carian linear.
Apa yang berlaku dalam satu pusingan?
Ambil dua item pertama. Jika yang kiri lebih besar, tukarkannya. Kemudian gerak satu tempat ke kanan dan bandingkan pasangan seterusnya. Teruskan sehingga pasangan terakhir.
Nilai yang lebih besar terus dibawa ke kanan, seperti gelembung yang naik. Itulah sebabnya, selepas satu pusingan, nilai terbesar berada pada kedudukan terakhir.
Bagaimana menukar dua nilai?
Pertukaran memerlukan tempat ketiga untuk menyimpan satu nilai, kerana menetapkan terus akan menimpanya:
Temp ← Data[I]
Data[I] ← Data[I + 1]
Data[I + 1] ← TempBerikut ialah satu pusingan dalam pseudokod untuk senarai lima item:
Swapped ← FALSE
FOR I ← 1 TO 4
IF Data[I] > Data[I + 1] THEN
Temp ← Data[I]
Data[I] ← Data[I + 1]
Data[I + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT IGelung hanya sampai 4 kerana perbandingan terakhir ialah kedudukan 4 dengan kedudukan 5.
Contoh berlangkah
Data = [6, 2, 9, 4, 1]. Jejak pusingan pertama.
| I | Pasangan dibandingkan | Tidak teratur? | Senarai selepas itu | Swapped |
|---|---|---|---|---|
| Mula | 6, 2, 9, 4, 1 | FALSE | ||
| 1 | 6 dan 2 | Ya, tukar | 2, 6, 9, 4, 1 | TRUE |
| 2 | 6 dan 9 | Tidak | 2, 6, 9, 4, 1 | TRUE |
| 3 | 9 dan 4 | Ya, tukar | 2, 6, 4, 9, 1 | TRUE |
| 4 | 9 dan 1 | Ya, tukar | 2, 6, 4, 1, 9 | TRUE |
Selepas satu pusingan, senarai ialah [2, 6, 4, 1, 9]. Tiga pertukaran dibuat. Nilai terbesar, 9, kini berada pada kedudukan 5, tetapi senarai belum tersusun, jadi pusingan lain diperlukan.
Pusingan kedua memberi [2, 4, 1, 6, 9]. Pusingan ketiga memberi [2, 1, 4, 6, 9]. Pusingan keempat memberi [1, 2, 4, 6, 9]. Pusingan kelima tidak membuat pertukaran, jadi Swapped kekal FALSE dan isihan berhenti.
Kesilapan yang perlu diawasi
Kesilapan lazim ialah menukar tanpa pemboleh ubah sementara:
Data[I] ← Data[I + 1]
Data[I + 1] ← Data[I]Ambil Data = [6, 2] dengan I = 1. Baris pertama menetapkan Data[1] kepada 2, memberi [2, 2]. Baris kedua kemudian menyalin Data[1], yang kini 2, ke dalam Data[2]. Hasilnya [2, 2], dan nilai 6 hilang.
Pembetulannya ialah menyimpan nilai pertama dalam Temp sebelum menimpanya. Semasa menjejak pertukaran, tulis nilai Temp dalam lajurnya sendiri supaya nilai yang hilang dapat dilihat.
Semak sendiri
1. Jejak satu pusingan pada [3, 1, 2]. Apakah senarai selepas itu, dan berapa pertukaran dibuat?
Show answer
Bandingkan 3 dan 1: tukar, memberi 1, 3, 2. Bandingkan 3 dan 2: tukar, memberi 1, 2, 3. Hasil [1, 2, 3] dengan 2 pertukaran.
2. Satu pusingan pada [4, 5, 6] berakhir dengan Swapped = FALSE. Apakah maksudnya?
Show answer
Tiada pasangan yang tidak teratur, jadi senarai sudah tersusun dan tiada pusingan lanjut diperlukan.
3. A = 4 dan B = 9. Tulis tiga baris yang menukarnya, kemudian nyatakan nilai akhir.
Show answer
Temp ← A (Temp = 4), A ← B (A = 9), B ← Temp (B = 4). Nilai akhir: A = 9, B = 4.
Ke mana selepas ini
Seterusnya, lihat bagaimana data tersimpan dipecahkan kepada bahagian dalam membaca rekod tanpa kehilangan sempadan medan. Pelatih jejak pseudokod terhad boleh menggerakkan satu pusingan supaya anda dapat membandingkan setiap keadaan senarai dengan jadual anda.
Jika pertukaran atau bendera masih bertindak di luar jangkaan dalam jawapan anda, guru kami boleh membantu melalui tuisyen Computer Science dalam talian satu dengan satu.