Asas Sains Komputer notesnota, bab 3

Algoritma

TextbookBuku teks Asas Sains Komputer Tingkatan 3 KSSM (cetakan pertama 2018), pageshalaman 60–111

What this chapter coversMatlamat bab ini

Murid boleh mengenal pasti ciri-ciri search (linear, binary) dan sort (bubble, bucket) (3.1.1)
Murid boleh menulis pseudokod dan melukis carta alir yang menunjukkan linear search dan binary search (3.1.2)
Murid boleh menulis pseudokod dan melukis carta alir yang menunjukkan bubble sort dan bucket sort (3.1.3)
Murid boleh mengesan dan membaiki ralat dalam pseudokod dan carta alir bagi penyelesaian masalah yang melibatkan search dan sort (3.1.4)
Murid boleh membandingkan algoritma search dan sort melalui pengecaman corak (3.1.5)
Murid boleh menghasilkan algoritma yang melibatkan gabungan teknik search dan sort (3.1.6)
Murid boleh menghasilkan algoritma yang melibatkan gabungan teknik search atau sort (3.1.7)

3.1Pembangunan algoritma

Apabila kita menempah tiket kapal terbang atau mencari bilik hotel dalam telefon pintar, aplikasi itu menggunakan teknik carian (search) dan isihan (sort). Kedua-dua teknik ini membantu kita mendapatkan maklumat dengan lebih mudah. Dalam bab ini kita mempelajari empat algoritma: linear search, binary search, bubble sort dan bucket sort.

Algoritma ialah satu siri langkah atau tindakan yang jelas yang perlu dilaksanakan untuk menghasilkan output yang dikehendaki.

Pengatur cara membina algoritma dahulu, kemudian menulis atur cara berpandukan algoritma itu. Algoritma boleh diwakili dengan pseudokod dan carta alir. Pembangunan algoritma ialah satu teknik pengitlakan yang melibatkan pembinaan langkah-langkah penyelesaian masalah (ms. 62).

Faedah mengkaji dan membangunkan algoritma:

Memahami bagaimana komputer memproses urutan tindakan yang perlu dilaksanakan.
Mempelajari cara menulis algoritma yang teratur, mudah dibaca dan difahami.
Mempelajari cara menulis algoritma dengan cekap.
Mempelajari cara melakukan penambahbaikan pada algoritma.

Pseudokod ialah perwakilan algoritma dalam bahasa yang boleh difahami. Carta alir ialah perwakilan algoritma dalam bentuk grafik (ms. 73).

Simbol carta alir dan kata kunci pseudokod

Pseudokod	Maksud	Simbol dalam carta alir
`Mula`, `Tamat`	Permulaan dan penamat algoritma	Terminal: MULA, TAMAT
`Setkan`, `Isytihar pemboleh ubah`	Memberi nilai kepada pemboleh ubah atau senarai; mengisytiharkan nama pemboleh ubah	Proses (segi empat tepat)
`Kira`, `temp = ...`	Mengira atau menukar nilai, contohnya `Kira i = i + 1`	Proses
`Masukkan`, `Papar`	Pengguna memasukkan nilai (input); komputer menunjukkan hasil (output)	Input / output (segi empat selari)
`Jika ... Jika tidak ... Tamat jika`	Struktur kawalan pilihan: membuat keputusan Ya atau Tidak	Keputusan (berlian) dengan cabang Ya dan Tidak
`for`, `while`	Struktur kawalan ulangan: langkah di dalamnya diulang selagi syarat benar	Keputusan dengan anak panah yang kembali ke atas
`Keluar gelung`, `Langkau ke Langkah n`	Menamatkan ulangan atau melompat ke langkah lain	Anak panah keluar dari gelung

Tanda: == sama dengan (membandingkan, contoh L[i] == T); = umpukan (contoh i = 0); <, >, >=, <= kurang daripada, lebih daripada, lebih atau sama, kurang atau sama.

Buku menulis item senarai dengan subskrip, contohnya L_i dan L_{j + 1}. Dalam nota ini ditulis L[i] dan L[j + 1]. Maksudnya sama: item pada indeks i dalam senarai L. Indeks bermula dengan 0, jadi item pertama ialah L[0] dan item terakhir ialah L[n - 1].

Jangan keliru antara = dan ==. i = 0 memberi nilai 0 kepada i. L[i] == T bertanya: adakah item itu sama dengan T?

3.1.1 Ciri-ciri search dan sort

Search dan sort hanya berlaku apabila terdapat satu senarai atau pangkalan data. Cara kita mencari buku di perpustakaan bergantung pada bagaimana buku-buku itu disusun (ms. 62).

(i) Search

Search ialah proses untuk mendapatkan suatu item tertentu yang terkandung dalam satu senarai.

Linear search

Linear search ialah satu teknik untuk mendapatkan item yang dikehendaki dalam satu senarai linear. Carian bermula dengan item pertama, kemudian item kedua, ketiga dan seterusnya sehingga item itu diperoleh. Jika tidak diperoleh sehingga carian selesai, carian ditamatkan tanpa hasil (ms. 63).

Contoh 3.1: mencari buah mangga (ms. 63)

Erina mencari buah mangga di lima bahagian ruang jualan. Bahagian pertama mengandungi pisang, bahagian kedua manggis dan bahagian ketiga mangga.

Lima bahagian ruang jualan buah-buahan: bahagian pertama pisang, kedua manggis, ketiga mangga, keempat buah naga dan kelima jambu — Bahagian pertama hingga kelima (Contoh 3.1, ms. 63).

Buku teks Asas Sains Komputer Tingkatan 3, ms. 63.

Bahagian pertama: pisang, bukan mangga. Teruskan.
Bahagian kedua: manggis, bukan mangga. Teruskan.
Bahagian ketiga: mangga. Carian dihentikan selepas 3 semakan.

Contoh 3.2: markah 90 dan ke atas (ms. 64 hingga 65)

Cikgu Aiman mencari murid Kelas 3 Utarid (27 orang) yang mendapat 90 markah dan ke atas. Carian bermula dengan nama pertama hingga nama terakhir, jadi semua 27 nama disemak. Hasilnya enam murid (Jadual 3.1):

Alif Qusyairi bin Muaz (98), Dhesigan a/l Subra (90), Moey Kam Seng (90), Monisa anak Balangan (90), Nur Ain Shazwani binti Amir Firdaus (98) dan Nur Alia Fariesya binti Zuhri (96).

Buku teks Asas Sains Komputer Tingkatan 3, ms. 64 hingga 65 (Jadual 3.1).

Ciri-ciri linear search:

Algoritma yang sangat mudah.
Item dalam senarai tidak perlu diisih dahulu.
Menyemak setiap item, jadi tidak begitu cekap jika senarai mengandungi banyak item.
Jika item yang dicari berada di akhir senarai atau tiada dalam senarai, semakan tetap berlangsung hingga item terakhir.
Sesuai untuk senarai yang mempunyai item yang sedikit (Rajah 3.1, ms. 72).

Uji Minda 3.1 dan 3.2 (ms. 65). Fikirkan satu situasi harian yang melibatkan linear search dan satu yang melibatkan binary search.

Tunjuk jawapanSembunyi jawapan

Linear search: mencari kasut sendiri di rak kasut yang tidak tersusun, atau mencari nama sendiri dalam senarai hadir yang tidak diisih. Binary search: mencari perkataan dalam kamus, atau mencari nama dalam buku panduan telefon yang tersusun mengikut abjad.

Binary search

Binary search ialah teknik carian yang melibatkan keputusan dwipilihan. Item dalam senarai mesti diisih dalam urutan menaik dahulu. Item di tengah senarai disemak. Separuh senarai yang tidak mengandungi item carian diabaikan, dan proses diulang pada separuh yang tinggal (ms. 65).

Semak item di tengah senarai. Jika sama dengan item carian, carian tamat.
Jika item carian lebih kecil, item tengah dan semua item di sebelah kanannya diabaikan.
Jika item carian lebih besar, item tengah dan semua item di sebelah kirinya diabaikan.
Ulang pada senarai yang tinggal. Jika tiada hasil apabila carian selesai, carian ditamatkan tanpa hasil.

Contoh 3.3: mencari nombor 35 (ms. 66 hingga 67)

Senarai ialah 12, 30, 35, 39, 42, 48, 50, 53, 62. Letakkan indeks bermula dengan 0. Indeks terkecil i = 0 dan indeks terbesar j = 8.

Indeks pertengahan: m = (i + j) / 2 = (0 + 8) / 2 = 4, iaitu item 42.

Langkah	i	j	m	L[m]	Keputusan
1	0	8	(0 + 8) / 2 = 4	42	35 < 42: j = 4 - 1 = 3
2	0	3	(0 + 3) / 2 = 1	30	35 > 30: i = 1 + 1 = 2
3	2	3	(2 + 3) / 2 = 2	35	35 = 35: jumpa

Jika titik tengah menghasilkan nombor perpuluhan, komputer membacanya sebagai nombor bulat terkecil. Contohnya 13 bahagi 5 ialah 2.6, maka komputer membaca item pada indeks 2 (ms. 66). Dalam Python ini ialah //, tetapi buku menulis (i + j)/2.

Contoh 3.4: mencari huruf J dalam buku panduan telefon (ms. 67 hingga 68)

Shalina mencari nama James. Halaman A hingga Z ialah senarai 26 huruf (indeks 0 hingga 25). Apabila binary search dijalankan pada huruf J, item tengah ialah M, F, I, K, J mengikut urutan:

i = 0, j = 25: m = 12 (M), J < M, j = 11. m = 5 (F), J > F, i = 6. m = 8 (I), J > I, i = 9. m = 10 (K), J < K, j = 9. m = 9 (J), jumpa.

Ini sama dengan halaman yang dibuka dalam buku teks: M, F, I, K, kemudian J. Setiap kali, separuh daripada halaman yang tinggal diabaikan.

Ciri-ciri binary search: lebih efisien dan menjimatkan masa berbanding linear search kerana tidak menyemak setiap item; sesuai untuk senarai yang banyak item; tetapi senarai mesti diisih menaik dahulu.

Binary search pada senarai yang belum diisih akan memberi hasil yang salah. Item yang ada boleh dianggap tiada kerana separuh senarai diabaikan secara salah.

Linear search atau binary search: berapa banyak semakan?

Pada senarai 10 item, linear search semak sehingga 10 item. Binary search tidak pernah semak lebih daripada 4 item. Perbezaan menjadi sangat besar apabila senarai panjang (nombor dalam jadual ini dikira, bukan dalam buku teks):

Semakan terbanyak (linear search, binary search): 10 item: 10, 4; 100 item: 100, 7; 1 000 item: 1 000, 10; 1 000 000 item: 1 000 000, 20. Bilangan semakan binary search ialah bahagian bulat bagi log₂ n, tambah 1 (tambahan, bukan dalam buku teks).

Aktiviti 3.1 (ms. 68). Senarai: 25, 10, 35, 45, 5, 30, 15, 40, 20. Cari nombor 5 dan nombor 40 dengan (a) linear search, (b) binary search. Bandingkan bilangan langkah.

Tunjuk jawapanSembunyi jawapan

(a) Linear search pada senarai asal: nombor 5 berada di indeks 4, jadi 5 semakan. Nombor 40 berada di indeks 7, jadi 8 semakan.

(b) Binary search memerlukan senarai diisih dahulu: [5, 10, 15, 20, 25, 30, 35, 40, 45]. Nombor 5: m = 4 (25), m = 1 (10), m = 0 (5), iaitu 3 semakan. Nombor 40: m = 4 (25), m = 6 (35), m = 7 (40), iaitu 3 semakan.

Justifikasi: binary search menggunakan lebih sedikit langkah bagi nombor di hujung, tetapi senarai perlu diisih dahulu.

(ii) Sort

Sort ialah proses mengisih atau menyusun item dalam suatu senarai linear mengikut urutan tertentu (menaik atau menurun) (ms. 69).

Contoh sort dalam kehidupan seharian: mengisih surat di pejabat pos mengikut negeri, menyusun nama murid mengikut abjad dan menyusun murid ke dalam barisan mengikut rumah sukan.

Bubble sort

Bubble sort ialah teknik pengisihan yang mudah. Dua item bersebelahan dibandingkan mulai dua item pertama hingga item terakhir. Untuk urutan menaik, kedua-dua item bertukar tempat jika item pertama lebih besar. Untuk urutan menurun, kedua-duanya bertukar jika item pertama lebih kecil (ms. 69).

Contoh 3.5: isihan menurun, senarai 4, 1, 9, 5, 3 (ms. 69 hingga 70)

Senarai 4, 1, 9, 5, 3. Pusingan pertama: 4 > 1 tidak tukar; 1 < 9 tukar [4, 9, 1, 5, 3]; 1 < 5 tukar [4, 9, 5, 1, 3]; 1 < 3 tukar [4, 9, 5, 3, 1]. Pusingan kedua: 4 < 9 tukar [9, 4, 5, 3, 1]; 4 < 5 tukar [9, 5, 4, 3, 1]; 4 > 3 tidak tukar; 3 > 1 tidak tukar.

Selepas langkah 4, semua item sudah dibandingkan sekali, tetapi senarai belum menurun. Maka perbandingan diulang dari awal (langkah 5 hingga 8). Pada akhirnya senarai ialah 9, 5, 4, 3, 1.

Uji Minda 3.3 (ms. 71). Isih 4, 7, 2, 5, 6 dalam urutan menaik dengan bubble sort. Tunjukkan langkah kerja.

Tunjuk jawapanSembunyi jawapan

Urutan menaik: tukar jika item pertama lebih besar.

Lelaran	Senarai
Asal	[4, 7, 2, 5, 6]
Lelaran 1	[4, 2, 5, 6, 7]
Lelaran 2	[2, 4, 5, 6, 7]

Hasil: 2, 4, 5, 6, 7. Lelaran 1: 4 > 7? tidak; 7 > 2? tukar; 7 > 5? tukar; 7 > 6? tukar.

Bucket sort

Bucket sort ialah teknik yang mengasingkan item dalam senarai ke dalam baldi (bucket). Kemudian item di dalam setiap baldi diisih dan disusun semula ke dalam senarai. Bilangan baldi bergantung pada pengatur cara dan bilangan item (ms. 71).

Contoh 3.6: isihan menaik huruf H, C, D, A, F, G, B, E, I, J (ms. 71)

Sediakan tiga baldi dan tetapkan julat: A hingga C, D hingga F, G hingga J.
Masukkan setiap huruf ke dalam baldi yang betul.
Isih huruf dalam setiap baldi (boleh guna bubble sort), kemudian cantumkan semula.

Tiga baldi: C A B, D F E dan H G I J sebelum diisih; A B C, D E F dan G H I J selepas diisih; senarai akhir A hingga J — Bucket sort dengan tiga baldi (Contoh 3.6, ms. 71). Baldi diisi mengikut urutan huruf dalam senarai asal.

Dalam bucket sort, item diisih dua kali. Isihan pertama: item dimasukkan ke dalam baldi mengikut julat. Isihan kedua: item dalam setiap baldi diisih mengikut urutan (ms. 86).

Perbandingan search dan sort (Rajah 3.1, ms. 72)

	Search	Sort
Tujuan	Mencari item tertentu dalam suatu senarai	Mengisih item dalam senarai mengikut urutan menaik atau menurun
Persamaan	Kedua-duanya memerlukan suatu senarai dan memerlukan algoritma
Senarai yang sedikit item	Linear search	Bubble sort
Senarai yang banyak item	Binary search	Bucket sort

Ingat pasangannya: Linear + Bubble = sedikit item; Binary + Bucket = banyak item.

3.1.2 Pseudokod dan carta alir: linear search dan binary search

Algoritma wujud dalam banyak aktiviti harian seperti memasak dan membasuh pakaian. Jika langkahnya tidak diikuti dengan betul, output tidak seperti yang dikehendaki. Pseudokod dan carta alir dibina dahulu supaya langkah jelas dan mudah difahami, dan ralat lebih mudah dikesan (ms. 73).

Di Tingkatan 1 dan 2 anda telah belajar struktur kawalan pilihan, struktur kawalan ulangan (for, while) dan cara mengesan ralat dalam pseudokod dan carta alir. Semuanya digunakan semula di sini.

(i) Linear search

Contoh 3.7: mencari satu nombor dalam senarai rawak (ms. 73 hingga 76)

Senarai: 10, 82, 5, 18, 27, 15, 44, 100, 42, 99 (senarai rawak: nombor tidak disusun).

Langkah 1: bina algoritma (Rajah 3.2).

Mula dengan item pertama dalam senarai.
Bandingkan item carian dengan item pertama.
Jika nilai item carian sama dengan nilai item pertama, carian dihentikan.
Jika tidak sama, ulang Langkah 2 hingga 4 dengan item yang berikutnya.
Carian tamat apabila item carian diperoleh atau apabila semua item telah disemak.

Langkah 2: kenal pasti pemboleh ubah.

L: senarai (List) (10 item: L[0] = 10, L[1] = 82, ..., L[9] = 99)
T: nilai item carian (Target) (dimasukkan oleh pengguna)
i: kedudukan (indeks) item dalam senarai (index) (0 hingga 9)
n: bilangan item dalam senarai (number) (10)

Huruf lain juga boleh digunakan untuk pemboleh ubah (ms. 74).

Pseudokod (Rajah 3.3):

1 Mula
2 Setkan senarai L = [10, 82, 5, 18, 27, 15, 44, 100, 42, 99]
3 Isytihar pemboleh ubah i, n, T
4 Setkan n = 10
5 Setkan i = 0
6 Masukkan nilai carian T
7 for i < n
  7.1 Jika L[i] == T
      7.1.1 Papar "Item ada dalam senarai"
      7.1.2 Langkau ke Langkah 9
  7.2 Jika tidak
      7.2.1 Kira i = i + 1
  7.3 Tamat jika
8 Jika i >= n
  8.1 Papar "Item tiada dalam senarai"
  8.2 Tamat jika
9 Tamat

Buku teks Asas Sains Komputer Tingkatan 3, ms. 74.

Carta alir linear search (Rajah 3.4, ms. 75). Nombor dalam bulatan sepadan dengan jadual di bawah.

(1) Senarai L diumpukkan dengan 10 nilai. (2) n = 10 (bilangan item). i = 0 (kedudukan item pertama). (3) Pengguna memasukkan nombor carian, disimpan dalam T. (4) Selagi i < n benar, carian dilakukan pada setiap item. (5) Jika L[i] sama dengan T, papar "Item ada dalam senarai" dan carian dihentikan. (6) Jika tidak sama, i = i + 1 dan proses diulang sehingga T dijumpai atau semua item disemak. (7) Jika i >= n, semua item telah disemak dan T tidak dijumpai. Papar "Item tiada dalam senarai".

i = i + 1 menunjukkan ciri linear: indeks bertambah 1 selagi syarat belum dipenuhi (ms. 75).

Jejak (trace) bagi T = 44: carian berhenti di indeks 6 selepas 7 semakan.

Nilai T	Kedudukan	Bilangan semakan	Output
10	indeks 0	1	Item ada dalam senarai
44	indeks 6	7	Item ada dalam senarai
99	indeks 9 (terakhir)	10	Item ada dalam senarai
90	tiada	10 (semua item)	Item tiada dalam senarai

Uji Minda 3.6 (ms. 75). (1) Jika T = 90, apakah output? (2) Jika T = 44, berapakah bilangan ulangan sehingga output dipaparkan?

Tunjuk jawapanSembunyi jawapan

(1) 90 tiada dalam senarai. Semua 10 item disemak, i menjadi 10, maka i >= n benar. Output: Item tiada dalam senarai.

(2) 44 berada pada indeks 6. Nilai i ditambah 1 sebanyak 6 kali (0 hingga 6) dan item disemak sebanyak 7 kali. Output: Item ada dalam senarai.

Aktiviti 3.3 (ms. 76). Senarai 1.3, 3.7, 4.8, 1.5, 2.5; cari 1.5 dengan linear search. Tulis pseudokod ringkas.

Tunjuk jawapanSembunyi jawapan

Item 1.5 berada pada indeks 3, jadi carian berhenti selepas 4 semakan.

Guna pseudokod linear search Rajah 3.3 dengan L = [1.3, 3.7, 4.8, 1.5, 2.5] dan n = 5.

(ii) Binary search

Binary search digunakan dalam situasi harian, contohnya mencari nombor telefon berdasarkan nama dalam buku panduan telefon, mencari makna perkataan dalam kamus, mencari kad rekod pesakit di klinik mengikut nombor kad pengenalan dan mencari fail penuntut di kolej (ms. 77).

Contoh 3.8: mencari satu abjad dalam senarai A hingga Z (ms. 77 hingga 80; buku menulis nombor contoh ini sebagai 2.8)

Langkah 1: bina algoritma (Rajah 3.5).

Pastikan item dalam senarai sudah diisih mengikut urutan menaik.
Lihat item yang berada di tengah senarai.
Bandingkan item carian dengan item di tengah senarai.
Jika sama, carian dihentikan.
Jika item carian kurang daripada item tengah, abaikan item tengah dan item selepasnya. Lihat senarai yang tinggal.
Jika item carian lebih daripada item tengah, abaikan item tengah dan item sebelumnya. Lihat senarai yang tinggal.
Ulang Langkah 2 hingga 6 sehingga item dijumpai atau carian selesai tanpa menjumpai item.

Langkah 2: kenal pasti pemboleh ubah.

L: senarai (26 item, A hingga Z)
n: bilangan item dalam senarai (26)
i: kedudukan item pertama (indeks terkecil) (0)
j: kedudukan item terakhir (indeks terbesar) = n - 1, kerana indeks bermula dengan 0 (25)
m: kedudukan item pertengahan ((i + j) / 2)
b: nilai item carian (dimasukkan oleh pengguna)

Pseudokod (Rajah 3.6, dengan syarat i <= j):

1 Mula
2 Setkan senarai L = [A, B, C, D ... Z]
3 Isytihar pemboleh ubah n, i, j, m, b
4 Setkan n = 26
5 Setkan i = 0
6 Setkan j = n - 1
7 Masukkan satu nilai carian b
8 while i <= j
  8.1 Setkan m = (i + j)/2
  8.2 Jika b == L[m]
      8.2.1 Papar "Item ada dalam senarai"
      8.2.2 Keluar gelung
  8.3 Jika tidak
      8.3.1 Jika b < L[m]
            8.3.1.1 Kira j = m - 1
      8.3.2 Jika tidak
            8.3.2.1 Kira i = m + 1
      8.3.3 Tamat jika
  8.4 Tamat jika
9 Tamat

Syarat gelung. Buku teks (Rajah 3.6, 3.7 dan jawapan Uji Kendiri 3.1) menulis while i < j. Syarat ini berhenti terlalu awal apabila tinggal satu item (i == j) kerana item itu tidak sempat disemak. Contohnya mencari huruf Q dalam A hingga Z: dengan i < j gelung berhenti pada i = 16 dan j = 16 tanpa memaparkan apa-apa, walaupun Q ada dalam senarai. Dengan i <= j, Q dijumpai. Nota ini dan carta alir di bawah menggunakan i <= j (seperti pseudokod Dayang Arni dalam Aktiviti 3.8, ms. 94). Jawapan dalam buku (ms. 222, 223 dan 224) juga menggunakan i < j, tetapi i <= j ialah bentuk yang tidak tertinggal item.

Carta alir binary search (Rajah 3.7, ms. 79) dengan syarat i <= j. Nombor dalam bulatan sepadan dengan jadual di bawah.

(1) Senarai L diumpukkan dengan A hingga Z. (2) i = 0 (item pertama), n = 26 (bilangan item), j = n - 1 = 25 (item terakhir). (3) Pengguna memasukkan item carian b. (4) Selagi masih ada item yang belum diabaikan, indeks pertengahan dikira dengan m = (i + j) / 2. (5) Jika b == L[m], papar "Item ada dalam senarai" dan carian dihentikan. (6) Jika b < L[m], item terakhir dikira semula: j = m - 1. Jika b > L[m], item pertama dikira semula: i = m + 1. Proses diulang.

Jejak bagi huruf Q (indeks 16):

Ulangan	i	j	m	L[m]	Keputusan
1	0	25	(0 + 25) / 2 = 12	M	Q > M: i = 12 + 1 = 13
2	13	25	(13 + 25) / 2 = 19	T	Q < T: j = 19 - 1 = 18
3	13	18	(13 + 18) / 2 = 15	P	Q > P: i = 15 + 1 = 16
4	16	18	(16 + 18) / 2 = 17	R	Q < R: j = 17 - 1 = 16
5	16	16	(16 + 16) / 2 = 16	Q	Q = Q: jumpa

Q dijumpai pada ulangan ke-5. Bagi huruf F (indeks 5): m = 12 (M), F < M, j = 11; m = 5 (F), jumpa pada ulangan ke-2.

Uji Minda 3.8 (ms. 79). (1) Apakah output jika b ialah abjad Q? (2) Jika b ialah F, berapakah bilangan ulangan?

Tunjuk jawapanSembunyi jawapan

(1) Q ada dalam senarai. Output: Item ada dalam senarai (selepas 5 ulangan dengan i <= j; lihat jadual jejak di atas).

(2) F dijumpai pada ulangan ke-2 (m = 12, M; kemudian m = 5, F).

Aktiviti 3.4 (ms. 80). Senarai 10, 20, 30, 40, 50, 60, 70. Cari 30 dengan binary search.

Tunjuk jawapanSembunyi jawapan

i = 0, j = 6. m = 3 (40): 30 < 40, j = 2. m = 1 (20): 30 > 20, i = 2. m = 2 (30): jumpa.

30 dijumpai pada indeks 2 selepas 3 semakan.

Aktiviti 3.5 (ms. 81). Permainan meneka nombor 1 hingga 100. Apakah kesimpulannya jika satu pihak meneka dengan linear search (1, 2, 3, ...) dan satu pihak dengan binary search?

Tunjuk jawapanSembunyi jawapan

Linear search boleh memerlukan sehingga 100 tekaan. Binary search (teka 50, kemudian 25 atau 75, dan seterusnya) memerlukan paling banyak 7 tekaan. Binary search jauh lebih pantas untuk senarai yang banyak dan sudah tersusun.

3.1.3 Pseudokod dan carta alir: bubble sort dan bucket sort

Sort ialah tugas yang sering digunakan dalam pengaturcaraan dan kehidupan seharian. Data yang sudah diisih menjadikan carian lebih cekap, percantuman lebih efisien dan pemprosesan data lebih mudah. Dalam set data yang besar, data berulang (duplikasi) lebih mudah dikesan dan dibuang atau dicantumkan jika data sudah diisih (ms. 81).

(i) Bubble sort

Bubble sort boleh menyenaraikan markah murid mengikut urutan menaik atau menurun. Markah tertinggi sentiasa bergerak ke permulaan senarai (isihan menurun), diikuti markah kedua tertinggi dan seterusnya. Nama "bubble" datang daripada buih yang lebih ringan terapung ke permukaan air (ms. 81 hingga 82).

Contoh 3.9: jarak lontaran lempar cakera (ms. 82 hingga 85)

Sepuluh peserta lempar cakera mencatat jarak lontaran (m): 28.2, 26, 26.5, 27.2, 30.4, 27, 31.4, 29.1, 27.4, 27.8. Cikgu Azmi mahu mengisih senarai dalam urutan menurun untuk menentukan pemenang.

Langkah 1: bina algoritma (Rajah 3.9).

Semak item pertama dengan item kedua dalam senarai.
Bandingkan kedua-dua item itu.
Jika kedua-duanya tidak mengikut urutan, tukarkan kedudukan kedua-duanya.
Ulang Langkah 2 hingga 3 dengan item kedua dan ketiga, kemudian ketiga dan keempat, hingga item terakhir.
Semak senarai sama ada semua item sudah berada di kedudukan yang betul.
Ulang Langkah 1 hingga 5 sehingga semua item telah diisih.

Langkah 4 dan langkah 6 memerlukan gelung: item bersebelahan dibandingkan sehingga dua item terakhir, dan senarai diisih berulang kali sehingga semua item berada dalam urutan yang betul.

Langkah 2: kenal pasti pemboleh ubah.

L: senarai yang mengandungi 10 item: L[0] = 28.2, L[1] = 26, ..., L[n - 1] = 27.8
n: bilangan item dalam senarai L (10)
i: bilangan lelaran (pusingan) dalam gelung luar
j: kedudukan item dalam senarai L (gelung dalam)
temp: menyimpan data secara sementara semasa menukar kedudukan dua item (daripada perkataan temporary)

Pseudokod (Rajah 3.10):

1 Mula
2 Setkan senarai L = [28.2, 26, 26.5, 27.2, 30.4, 27, 31.4, 29.1, 27.4, 27.8]
3 Isytihar pemboleh ubah i, j, n, temp
4 Setkan n = 10
5 Setkan i = 0
6 Setkan temp = 0
7 for i < n - 1
  7.1 Setkan j = 0
  7.2 for j < n - i - 1
      7.2.1 Jika L[j] > L[j + 1]
            7.2.1.1 temp = L[j]
            7.2.1.2 L[j] = L[j + 1]
            7.2.1.3 L[j + 1] = temp
      7.2.2 Tamat jika
      7.2.3 Kira j = j + 1
  7.3 Kira i = i + 1
8 Papar senarai
9 Tamat

Buku teks Asas Sains Komputer Tingkatan 3, ms. 83.

Pseudokod dalam buku menggunakan L[j] > L[j + 1]. Syarat ini menyusun menaik (nombor kecil di hadapan). Untuk isihan menurun seperti keperluan Cikgu Azmi, tukar kepada L[j] < L[j + 1]. Ingat: menaik = tukar jika kiri lebih besar; menurun = tukar jika kiri lebih kecil.

Carta alir bubble sort: dua gelung for, i kurang daripada n tolak 1, j kurang daripada n tolak i tolak 1, jika L[j] lebih besar L[j+1] tukar guna temp, j = j + 1, i = i + 1, papar senarai, TAMAT — Carta alir bubble sort (Rajah 3.11, ms. 84). Nombor dalam bulatan sepadan dengan jadual di bawah.

(1) Senarai L diumpukkan dengan 10 nilai. (2) n = 10 (bilangan item), i = 0 (lelaran pertama), temp = 0 (data sementara untuk pertukaran). (3) Gelung for luar menentukan bilangan lelaran: i < n - 1. (4) j = 0, iaitu kedudukan item pertama. (5) Gelung for dalam memastikan setiap pasangan bersebelahan dibandingkan: L[0] dengan L[1], L[1] dengan L[2], dan seterusnya (j < n - i - 1). (6) Jika L[j] lebih besar daripada L[j + 1], kedudukan kedua-duanya ditukar. (7) Pertukaran guna temp supaya nilai kedua-dua item tidak menjadi sama. (8) j = j + 1: bandingkan pasangan seterusnya. (9) i = i + 1: mulakan lelaran seterusnya apabila semua pasangan sudah dibandingkan. (10) Apabila semua lelaran selesai, senarai yang telah diisih dipaparkan.

Bagaimana pertukaran dengan temp berfungsi

Bayangkan segelas susu dan secawan kopi. Untuk menukar kandungannya, anda perlukan bekas ketiga (Uji Minda 3.10). temp ialah bekas ketiga itu. Jika L[j] = 11 dan L[j + 1] = 5:

temp = L[j]: temp = 11. L[j] = L[j + 1]: L[j] = 5. L[j + 1] = temp: L[j + 1] = 11. Hasil: L[j] = 5 dan L[j + 1] = 11.

Urutan tiga baris pertukaran mesti betul. Jika L[j] = L[j + 1] ditulis dahulu tanpa menyimpan L[j] dalam temp, nilai asal L[j] hilang dan kedua-dua item menjadi sama.

Jejak bubble sort: satu lelaran terperinci

Senarai kecil [11, 5, 77, 8, 44, 7] diisih menaik. Lelaran 1 membandingkan 5 pasangan (n - i - 1 = 5):

Lelaran 1 (item terbesar, 77, "terapung" ke hujung): 11 > 5 tukar [5, 11, 77, 8, 44, 7]; 11 > 77 tidak; 77 > 8 tukar [5, 11, 8, 77, 44, 7]; 77 > 44 tukar [5, 11, 8, 44, 77, 7]; 77 > 7 tukar [5, 11, 8, 44, 7, 77].

Selepas setiap lelaran, item yang paling besar daripada baki item berada di kedudukan akhirnya. Itulah sebabnya gelung dalam j < n - i - 1 semakin pendek.

Pseudokod dalam buku sentiasa menjalankan n - 1 lelaran dan membuat n(n - 1) / 2 perbandingan sepenuhnya. Bagi 6 item: 5 + 4 + 3 + 2 + 1 = 15 perbandingan. Bagi 10 item: 45 perbandingan. Senarai di atas sudah terisih selepas lelaran 4, tetapi lelaran 5 tetap dijalankan.

Hasil bagi Contoh 3.9 (menurun, dengan L[j] < L[j + 1]):

Lelaran 1: [28.2, 26.5, 27.2, 30.4, 27, 31.4, 29.1, 27.4, 27.8, 26]. Lelaran 2: [28.2, 27.2, 30.4, 27, 31.4, 29.1, 27.4, 27.8, 26.5, 26]. Senarai terisih sejak lelaran 6; lelaran 7 hingga 9 tiada perubahan.

Senarai menurun: [31.4, 30.4, 29.1, 28.2, 27.8, 27.4, 27.2, 27, 26.5, 26]. Jarak terjauh ialah 31.4 m. Bilangan perbandingan: 45. Dengan L[j] > L[j + 1] (menaik) hasilnya ialah [26, 26.5, 27, 27.2, 27.4, 27.8, 28.2, 29.1, 30.4, 31.4].

Uji Minda 3.9 (ms. 82). Apakah yang berlaku jika dua murid memperoleh jarak lontaran yang sama?

Tunjuk jawapanSembunyi jawapan

Syarat L[j] > L[j + 1] (atau < untuk menurun) bernilai palsu apabila dua nilai sama, jadi tiada pertukaran. Kedua-dua murid kekal pada kedudukan masing-masing dalam senarai.

Aktiviti 3.6 (ms. 85). Lengkapkan pseudokod bubble sort yang tidak lengkap selepas for i < n - 1.

Tunjuk jawapanSembunyi jawapan

Tulis semula baris 7.1 hingga 9 Rajah 3.10: Setkan j = 0; for j < n - i - 1 dengan pertukaran temp jika L[j] > L[j + 1]; Kira j = j + 1; Kira i = i + 1; Papar senarai; Tamat.

(ii) Bucket sort

Bucket sort menyusun item dalam senarai mengikut kategori. Item dimasukkan ke dalam baldi mengikut kategori yang ditetapkan. Kemudian item di dalam setiap baldi diisih mengikut urutan menaik atau menurun, dan dicantumkan semula ke dalam senarai (ms. 86).

Contoh 3.10: mengisih nama ahli jawatankuasa (ms. 86 hingga 89)

Qistina, Setiausaha Rumah Sukan Seri Usaha, mengisih senarai nama 15 orang ahli jawatankuasa mengikut abjad dengan bucket sort.

Langkah 1: bina algoritma (Rajah 3.12).

Wujudkan beberapa baldi untuk menyimpan item secara sementara.
Tentukan julat bagi setiap baldi.
Masukkan setiap item ke dalam baldi berdasarkan julat.
Isih item di dalam setiap baldi.
Selepas semua baldi diisih, cantumkan item dan masukkan semula ke dalam senarai.

Bucket sort amat berguna untuk senarai yang amat besar. Ia digunakan bersama isihan lain (misalnya bubble sort) untuk mengisih item dalam setiap baldi (ms. 86).

Langkah 2: kenal pasti pemboleh ubah.

L: senarai nama yang perlu diisih
i: kedudukan item dalam senarai L
n: bilangan item dalam L (15)
nB: bilangan baldi yang diperlukan
j: kedudukan baldi

Bilangan baldi boleh ditentukan dengan formula nB = had atas √n (had atas bermaksud dibundarkan ke atas kepada nombor bulat).

Contoh: n = 10, √10 = 3.162, nB = 4; n = 15, √15 = 3.873, nB = 4; n = 30, √30 = 5.477, nB = 6.

Buku memberi contoh 20 item: √20 = 4.472, maka 5 baldi diperlukan (ms. 87). Formula ialah panduan; pengatur cara boleh menetapkan bilangan baldi (Contoh 3.6 menggunakan 3 baldi untuk 10 huruf).

Pseudokod (Rajah 3.13):

1 Mula
2 Setkan senarai L = [Hilmi, Anas, Siti, ..., Maisara]
3 Setkan senaraiBaharu[ ]
4 Isytihar pemboleh ubah i, j, n, nB
5 Setkan n = 15
6 Setkan nB = bilangan baldi
7 Wujudkan baldi kosong
8 Masukkan item ke dalam baldi
9 Setkan i = 0
10 for i < n
   10.1 Masukkan senarai[i] ke dalam Baldi
   10.2 Kira i = i + 1
11 Setkan j = 0
12 for j < nB
   12.1 Jika Baldi[j] kosong
        12.1.1 Kira j = j + 1
   12.2 Jika tidak
        12.2.1 Isih item
        12.2.2 Kira j = j + 1
13 Cantum dan masukkan item-item ke dalam senaraiBaharu[ ]
14 Papar senaraiBaharu[ ]
15 Tamat

Buku teks Asas Sains Komputer Tingkatan 3, ms. 87.

Carta alir bucket sort: senarai L dan senaraiBaharu, wujudkan baldi kosong, gelung i kurang daripada n memasukkan item ke dalam baldi, gelung j kurang daripada nB menyemak Baldi[j] kosong atau isih item, cantum ke dalam senaraiBaharu, papar, TAMAT — Carta alir bucket sort (Rajah 3.14, ms. 88). Nombor dalam bulatan sepadan dengan jadual di bawah.

(1) Senarai L diumpukkan dengan item yang akan diisih. (2) senaraiBaharu[ ] disediakan untuk menyimpan item yang telah diisih. (3) n = 15 (bilangan item) dan nB = bilangan baldi yang diperlukan. (4) Wujudkan baldi kosong supaya item boleh dimasukkan; kemudian mulakan memasukkan item ke dalam baldi. (5) i = 0, kedudukan item pertama dalam senarai. (6) Selagi i < n, setiap senarai[i] dimasukkan ke dalam baldi yang betul, kemudian i = i + 1. (7) Selepas semua item dimasukkan, j = 0, kedudukan baldi pertama. (8) Selagi j < nB, semak Baldi[j] sama ada kosong atau tidak. (9) Jika Baldi[j] tidak kosong, item di dalamnya diisih (contohnya dengan bubble sort), kemudian j = j + 1. (10) Jika Baldi[j] kosong, terus ke baldi seterusnya. (11) Apabila semua baldi disemak, item dalam setiap baldi dicantumkan ke dalam senaraiBaharu[ ], dipaparkan, dan atur cara tamat.

Contoh dengan nombor: 10 markah, 4 baldi

Markah: [47, 12, 85, 33, 91, 5, 68, 29, 54, 76]. nB = had atas √10 = 4. Julat baldi: 0 hingga 24, 25 hingga 49, 50 hingga 74 dan 75 hingga 100.

Baldi	Selepas dimasukkan	Selepas diisih (menaik)
Baldi 1 (0 hingga 24)	[12, 5]	[5, 12]
Baldi 2 (25 hingga 49)	[47, 33, 29]	[29, 33, 47]
Baldi 3 (50 hingga 74)	[68, 54]	[54, 68]
Baldi 4 (75 hingga 100)	[85, 91, 76]	[76, 85, 91]

Cantumkan baldi 1 hingga 4: [5, 12, 29, 33, 47, 54, 68, 76, 85, 91].

Untuk isihan menurun, cantum baldi bermula dengan baldi yang julatnya tertinggi, dan isih setiap baldi secara menurun.

Aktiviti 3.7 (ms. 89). Isih 2, 9, 4, 6, 7, 1, 10, 5, 3, 8 dalam urutan menurun dengan bucket sort.

Tunjuk jawapanSembunyi jawapan

10 item, maka nB = had atas √10 = 4. Julat: 1 hingga 3, 4 hingga 6, 7 hingga 9, 10 hingga 12.

Baldi 1 [2, 1, 3] menjadi [3, 2, 1]; baldi 2 [4, 6, 5] menjadi [6, 5, 4]; baldi 3 [9, 7, 8] menjadi [9, 8, 7]; baldi 4 [10].

Cantum dari baldi 4 ke baldi 1: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1].

3.1.4 Mengesan dan membaiki ralat dalam pseudokod dan carta alir

Jika terdapat ralat dalam pseudokod atau carta alir, atur cara tidak menghasilkan output yang dikehendaki. Sebelum atur cara diuji, pseudokod dan carta alir disemak dahulu supaya semua ralat dapat dikesan dan dibaiki (ms. 90).

Semakan meja (desk checking): menyemak pseudokod atau carta alir di atas kertas dengan nilai sebenar, tanpa menjalankan atur cara.

Semakan langkah demi langkah (stepping through): mengikuti pelaksanaan satu langkah pada satu masa dan menyemak nilai pemboleh ubah selepas setiap langkah.

Kedua-dua teknik boleh ditunjukkan dengan jadual jejak (trace table): satu baris bagi setiap langkah, satu lajur bagi setiap pemboleh ubah.

(i) Ralat dalam algoritma search

Contoh 3.11: pseudokod Melanie (ms. 90 hingga 93)

Melanie membina atur cara untuk mencari dan memaparkan nilai 8 dalam senarai 3, 7, 2, 9, 6, 4, 1, 5, 8, 10, 11, 13. Apabila disemak, atur cara hanya menyemak nilai pertama dan semakan berulang tanpa memaparkan apa-apa.

Pseudokod Melanie (Rajah 3.15):

1 Mula
2 Setkan senarai L = [3, 7, 2, 9, 6, 4, 1, 5, 8, 10, 11, 13]
3 Isytihar pemboleh ubah i, n, T
4 Setkan i = 0
5 Setkan n = 12
6 for i < n
  6.1 Jika L[i] == T
      6.1.1 Papar n
      6.1.2 Keluar gelung
  6.2 Jika tidak
      6.2.1 Ulang Langkah 6
  6.3 Tamat jika
7 Tamat

Jadual jejak (semakan langkah demi langkah) bagi T = 8 (anggap T = 8 telah diketahui):

Ulangan 1, 2, 3 ...: i kekal 0, L[0] = 3 bukan 8, jadi item pertama disemak berulang selama-lamanya.

Tiga ralat dijumpai (Rajah 3.17 dan 3.18):

Ralat	Masalah	Pembaikan
A	Tiada langkah Masukkan nilai carian T	Tambah `Masukkan satu nilai carian T` supaya T (contohnya 8) diketahui
B	`Papar n` memaparkan bilangan item (12), bukan item yang dicari	Tukar kepada `Papar T`, kerana T ialah nilai carian
C	`Ulang Langkah 6` tidak mengubah i, jadi item pertama disemak berulang kali	Tukar kepada `Kira i = i + 1` supaya item seterusnya disemak

Dua carta alir bersebelahan: carta alir Melanie dengan tiga ralat A, B dan C, dan carta alir yang dibaiki dengan Masukkan T, Papar T dan i = i + 1 — Carta alir Melanie (Rajah 3.16 dan 3.18) dan versi yang dibaiki (Rajah 3.20). Ralat A: tiada input T. Ralat B: Papar n. Ralat C: tiada i = i + 1.

Pseudokod yang dibaiki (Rajah 3.19):

1 Mula
2 Setkan senarai L = [3, 7, 2, 9, 6, 4, 1, 5, 8, 10, 11, 13]
3 Isytihar pemboleh ubah i, n, T
4 Setkan i = 0
5 Setkan n = 12
6 Masukkan satu nilai carian T
7 for i < n
  7.1 Jika L[i] == T
      7.1.1 Papar T
      7.1.2 Keluar gelung
  7.2 Jika tidak
      7.2.1 Kira i = i + 1
  7.3 Tamat jika
8 Tamat

Selepas dibaiki, T = 8 dijumpai pada indeks 8 selepas 9 semakan, dan output ialah 8.

Uji Minda 3.12 (ms. 91). Apakah jenis ralat yang dilakukan oleh Melanie?

Tunjuk jawapanSembunyi jawapan

Ralat logik: atur cara dapat dijalankan tetapi langkah-langkahnya tidak menghasilkan output yang dikehendaki (tiada input, output yang salah, dan ulangan yang tidak berubah).

Uji Minda 3.13 (ms. 93). Adakah semakan meja sesuai digunakan untuk mengesan ralat dalam Contoh 3.11?

Tunjuk jawapanSembunyi jawapan

Ya. Senarai hanya 12 item dan langkahnya sedikit, maka jadual jejak di atas kertas dapat menunjukkan bahawa i kekal 0. Ralat dikesan tanpa menjalankan atur cara.

Uji Minda 3.14 (ms. 94). Apakah yang berlaku jika syarat Langkah 7 dalam pseudokod yang dibaiki ditukar kepada for i <= n?

Tunjuk jawapanSembunyi jawapan

Senarai mempunyai 12 item dengan indeks 0 hingga 11, tetapi n = 12. Jika i <= n, i boleh menjadi 12 dan L[12] tidak wujud (di luar julat). Ini menyebabkan ralat apabila nilai carian tiada dalam senarai. Untuk T = 8, item dijumpai pada indeks 8 sebelum itu, jadi ralat tidak muncul. Syarat yang betul ialah i < n.

Aktiviti 3.8 (ms. 94). Dayang Arni mencari 58 dalam 1, 6, 10, 18, 20, 40, 58, 67, 74, 87, 99. Kenal pasti tiga ralat dalam pseudokodnya (pemboleh ubah indeksAwal, indeksAkhir, nilaiTengah, nilaiCari).

Tunjuk jawapanSembunyi jawapan

Tiada langkah Masukkan nilai carian: nilaiCari tidak diisytiharkan dan tidak diberi nilai.
indeksTengah dikira pada Langkah 6.1 tetapi tidak diisytiharkan, dan nilaiTengah (yang diisytiharkan) tidak pernah diberi nilai. Tambah nilaiTengah = L[indeksTengah].
Langkah 6.2 menulis nilaiTengah = nilaiCari. Untuk membandingkan, guna ==.

Selepas dibaiki, mencari 58: i = 0, j = 10, m = 5 (40); i = 6; m = 8 (74); j = 7; m = 6 (58), dijumpai selepas 3 ulangan.

(ii) Ralat dalam algoritma sort

Contoh 3.12: bubble sort Soon Huat (ms. 95 hingga 99)

Soon Huat mahu mengisih 11, 5, 77, 8, 44, 7 dalam urutan menaik. Output yang dikehendaki: 5, 7, 8, 11, 44, 77. Output yang diperoleh: 77, 44, 11, 8, 7, 5 (menurun!).

Pseudokodnya sama dengan Rajah 3.10 tetapi dengan syarat pertukaran yang berbeza (Rajah 3.21):

7.2.1 Jika L[j] < L[j + 1]
      7.2.1.1 temp = L[j]
      7.2.1.2 L[j] = L[j + 1]
      7.2.1.3 L[j + 1] = temp

Semakan langkah demi langkah: syarat L[j] < L[j + 1] menukar jika item kiri lebih kecil. Itu isihan menurun.

Lelaran 1: [11, 77, 8, 44, 7, 5]. Lelaran 2: [77, 11, 44, 8, 7, 5]. Lelaran 3: [77, 44, 11, 8, 7, 5], dan seterusnya menurun.

Ralat: syarat yang perlu disemak ialah L[j] > L[j + 1] supaya dua item bersebelahan ditukar dan berada dalam urutan menaik (Rajah 3.23 dan 3.24).

Pembaikan (Rajah 3.25 dan 3.26):

7.2.1 Jika L[j] > L[j + 1]
      7.2.1.1 temp = L[j]
      7.2.1.2 L[j] = L[j + 1]
      7.2.1.3 L[j + 1] = temp

Dengan pembaikan, lelaran 1 hingga 4 menghasilkan [5, 11, 8, 44, 7, 77], [5, 8, 11, 7, 44, 77], [5, 8, 7, 11, 44, 77] dan [5, 7, 8, 11, 44, 77]; lelaran 5 tiada perubahan.

Hasil akhir 5, 7, 8, 11, 44, 77, 15 perbandingan dan 8 pertukaran.

Dalam carta alir yang dibaiki (Rajah 3.26, ms. 99), kotak pertukaran tertulis Li = Lj + 1. Ini salah cetak dalam buku. Yang betul ialah L[j] = L[j + 1], seperti dalam pseudokod Rajah 3.25.

Aktiviti 3.9: carta alir bucket sort Nurul (ms. 100)

Nurul mengisih 30 keping syiling (5 sen, 10 sen, 20 sen dan 50 sen) dengan bucket sort. Carta alirnya tidak memaparkan senarai yang telah diisih.

Semakan: bandingkan dengan Rajah 3.14. Selepas langkah Cantumkan dan masukkan item-item ke dalam senaraiBaharu[ ], carta alir Nurul terus ke TAMAT. Langkah Papar senaraiBaharu[ ] tertinggal.

Pembaikan: tambah kotak output Papar senaraiBaharu[ ] antara langkah mencantum dan TAMAT.

3.1.5 Pengecaman corak dalam algoritma search dan sort

Pengecaman corak ialah satu teknik untuk mengenal pasti ciri-ciri, struktur, bentuk input serta output dan sebagainya dalam sesuatu masalah. Ia melibatkan perbandingan corak antara masalah yang serupa atau sama untuk mencari persamaan dan perbezaan (ms. 101).

Jika corak masalah baharu sama dengan masalah lain yang sudah ada penyelesaian, pengatur cara boleh menggunakan penyelesaian itu atau menjadikannya asas untuk algoritma yang lebih baik.

Ciri	Algoritma search	Algoritma sort
Tujuan	Mencari suatu item dalam senarai	Mengisih item dalam senarai mengikut urutan menaik atau menurun
Apa yang dibandingkan	Item carian dengan item tertentu dalam senarai	Dua item bersebelahan atau item dalam julat baldi
Senarai	Boleh digunakan untuk senarai yang telah diisih atau belum diisih (binary search perlu senarai terisih)	Digunakan untuk senarai yang belum diisih
Bila berhenti	Apabila item dijumpai atau semua item telah disemak	Apabila semua item berada dalam urutan yang betul
Persamaan	Kedua-duanya menggunakan senarai dan menggunakan gelung

Berdasarkan Rajah 3.27, ms. 101.

Aktiviti 3.10 (ms. 102). Algoritma 1: wujudkan beberapa baldi, tentukan julat, masukkan item ke dalam baldi, isih item dalam setiap baldi, cantumkan. Algoritma 2: pastikan item diisih menaik, lihat item tengah, bandingkan, abaikan separuh senarai, ulang. Yang manakah search dan sort?

Tunjuk jawapanSembunyi jawapan

Algoritma 1 ialah sort (bucket sort) kerana item diasingkan ke dalam baldi, diisih dan dicantumkan semula. Algoritma 2 ialah search (binary search) kerana item tengah dibandingkan dengan item carian dan separuh senarai diabaikan.

Persamaan: kedua-duanya memerlukan senarai dan langkah yang berulang (gelung). Perbezaan: sort menukar susunan senarai; search hanya mencari item dan tidak mengubah senarai.

3.1.6 Algoritma bagi gabungan search dan sort

Kadangkala aktiviti mencari dan mengisih memerlukan gabungan algoritma search dan sort. Pengatur cara memilih gabungan teknik yang sesuai supaya output seperti yang diingini, dan penyelesaian lebih pantas serta mudah (ms. 102).

Contoh 3.13: nelayan memilih ikan (ms. 103)

Naikkan pukat ke atas kapal.
Cari ikan-ikan berkualiti yang mempunyai nilai dalam pasaran.
Jika ikan tidak berkualiti, lepaskan semula ke laut.
Isih ikan-ikan mengikut jenis.

Di sini proses carian dilakukan dahulu, kemudian proses isihan (Rajah 3.28).

Aktiviti 3.11: isih dahulu, kemudian cari (ms. 103)

Senarai: 16, 5, 27, 13, 9, 1, 6. Isihkan senarai, kemudian cari nombor 13.

Isih: hanya 7 item, jadi bubble sort sesuai. Hasil menaik: [1, 5, 6, 9, 13, 16, 27].
Cari: senarai sudah terisih, maka binary search boleh digunakan. 13 dijumpai pada indeks 4 selepas 3 semakan (9, 16, 13).

Perbandingan: linear search terus pada senarai asal menjumpai 13 selepas 4 semakan. Untuk satu carian pada senarai kecil, ia mungkin lebih ringkas. Untuk senarai yang besar atau dicari berkali-kali, isih dahulu kemudian binary search lebih berbaloi.

Uji Minda 3.15 (ms. 103). Bolehkah aktiviti dalam Contoh 3.13 dimulakan dengan mengisih ikan mengikut jenis, kemudian mencari ikan berkualiti?

Tunjuk jawapanSembunyi jawapan

Boleh, hasil akhir sama, tetapi kurang cekap. Ikan yang tidak berkualiti akan dilepaskan semula ke laut; jika semua ikan diisih dahulu, masa dibazirkan mengisih ikan yang akhirnya dilepaskan. Mencari dahulu mengurangkan bilangan ikan yang perlu diisih.

3.1.7 Algoritma bagi gabungan search atau sort

Gabungan satu teknik carian dengan teknik carian yang lain, atau satu teknik isihan dengan teknik isihan yang lain, juga sering digunakan (ms. 104).

Contoh 3.14: gabungan dua teknik search (ms. 104 hingga 105)

Naresh mencari buku rujukan operasi aritmetik di perpustakaan yang menggunakan Sistem Perpuluhan Dewey (DDC). Algoritmanya (Rajah 3.30):

Masuk ke perpustakaan.
Lihat carta DDC.
Cari nombor rak berlabel 500 Sains Tulen, dan pergi ke rak itu.
Cari bahagian berlabel 510 Matematik.
Cari bahagian berlabel 513 Aritmetik.
Cari bahagian berlabel 513.2 Operasi.
Cari buku yang dikehendaki. Tamat.

Mencari	Teknik	Sebab (daripada buku)
Rak 500 Sains Tulen	Binary search	Terdapat lebih 900 label pada carta DDC
Bahagian 510 Matematik	Linear search	Berada di rak pertama bagi label 500
Bahagian 513 Aritmetik	Binary search	Berada di tengah-tengah label antara 510 hingga 519
Bahagian 513.2 Operasi dan buku	Linear search	Hanya beberapa item yang tinggal

Contoh 3.15: gabungan dua teknik sort (ms. 105)

Adila, pembantu klinik, menyusun fail pesakit mengikut tahun kelahiran, dan bagi setiap tahun, mengikut abjad nama pesakit (Rajah 3.31).

Semak tahun kelahiran pada fail pesakit.
Masukkan fail ke dalam beberapa kotak mengikut tahun kelahiran (bucket sort, kerana pesakit pelbagai peringkat umur).
Isih fail dalam setiap kotak mengikut abjad nama (bubble sort).

Aktiviti 3.12 (ms. 106). Amira mencari dewan D (daripada 6 dewan) dan meja bernombor 38 (60 meja, bernombor 1 hingga 60 menaik). Teknik carian apa yang sesuai?

Tunjuk jawapanSembunyi jawapan

Dewan D: hanya 6 dewan (A hingga F), maka linear search: A, B, C, D (4 semakan).

Meja 38: 60 meja bernombor menaik (sudah terisih), maka binary search. Nombor meja yang disemak: 30, 45, 37, 41, 39, 38, iaitu 6 semakan sahaja berbanding sehingga 60 semakan dengan linear search.

Aktiviti 3.13 (ms. 106). Matthew perlu mengasingkan surat mengikut rumah bernombor ganjil dan genap, kemudian mengisih surat mengikut urutan menaik. Gabungan isihan apa yang sesuai?

Tunjuk jawapanSembunyi jawapan

Gunakan bucket sort dengan dua baldi (nombor ganjil dan nombor genap) untuk mengasingkan surat, kemudian guna bubble sort untuk mengisih surat dalam setiap baldi mengikut nombor rumah menaik. Cantumkan semula surat ikut urutan yang dikehendaki.

Semak semula Uji Kendiri 3.1 (ms. 107)

Soalan 2. Senarai 6, 8, 10, 12, 14, 16, 18, 20. Cari 14 dengan binary search.

Tunjuk jawapanSembunyi jawapan

n = 8, i = 0, j = 7. m = 3 (12): 14 > 12, i = 4. m = 5 (16): 14 < 16, j = 4. m = 4 (14): jumpa. 3 ulangan; 14 berada pada indeks 4.

Pseudokod sama dengan Rajah 3.6 (syarat while i <= j) dengan L = [6, 8, 10, 12, 14, 16, 18, 20], n = 8, j = 7.

Soalan 6. Jessica menerima kad bernombor 1 hingga 100 secara rawak. Dia mesti mencari semua kad yang mengandungi digit 5 dan mengisihnya menurun. Pilih teknik dan beri hasil.

Tunjuk jawapanSembunyi jawapan

Cari: linear search kerana semua 100 kad perlu disemak (tiada susunan, dan setiap kad diuji untuk digit 5). Isih: bubble sort atau bucket sort pada kad yang dijumpai (19 kad).

Kad yang mengandungi digit 5: [5, 15, 25, 35, 45, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 65, 75, 85, 95].

Isihan menurun: [95, 85, 75, 65, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 45, 35, 25, 15, 5].

Jawapan buku (ms. 223) hanya menyenaraikan 5, 15, 25, 35, 45, 55, 65, 75, 85, 95. Nombor 50 hingga 59 turut mengandungi digit 5, maka senarai lengkap ialah 19 kad.

Dua kunci jawapan buku (ms. 223 dan 224) tidak tepat. Pentaksiran 3, soalan objektif 7: lelaran pertama isihan menurun bagi [3, 10, 8, 9, 4] ialah [10, 8, 9, 4, 3], bukan pilihan C [10, 8, 9, 3, 4]. Soalan penyelesaian masalah 2: pseudokod kunci menulis 9 item (tanpa 46) tetapi n = 10 dan j = 9; senarai soalan mempunyai 10 item.

Rumusan bab 3

Linear search: semak satu demi satu, senarai tidak perlu diisih, sesuai untuk senarai sedikit item. Binary search: bandingkan dengan item tengah dan abaikan separuh, senarai mesti diisih menaik, sesuai untuk senarai banyak item. Bubble sort: bandingkan pasangan bersebelahan dan tukar dengan temp, sesuai untuk senarai sedikit item. Bucket sort: asingkan ke dalam baldi mengikut julat, isih setiap baldi, cantum semula (nB = had atas √n), sesuai untuk senarai banyak item.

Pseudokod dan carta alir dibina dahulu. Kesan ralat dengan semakan meja atau semakan langkah demi langkah.
Pengecaman corak: search dan sort sama-sama menggunakan senarai dan gelung.
Gabungan search dan sort: isih dahulu supaya binary search boleh digunakan; atau cari dahulu supaya item yang perlu diisih lebih sedikit.