🔎

ASK · TINGKATAN 3 · BAB 3

Algoritma Search dan Sort

📚 6 pelajaran · ⏱️ Anggaran 60 minit

Linear search, binary search, bubble sort, bucket sort dan pengesanan ralat algoritma.

1Fahami konsep
2Lihat contoh
3Cuba aktiviti
4Semak kendiri
5Uji dengan kuiz

Algoritma Search dan Sort

🎯 Hasil Pembelajaran

Membezakan linear dan binary search
Mengesan langkah bubble dan bucket sort
Membina pseudokod carian/isihan
Membaiki ralat algoritma

Konsep Utama

Linear search menyemak item satu demi satu dan sesuai untuk data tidak tersusun. Binary search membahagi ruang carian kepada dua tetapi memerlukan data telah diisih. Bubble sort menukar item bersebelahan yang salah susunan.

Perbandingan cara linear search dan binary search

Contoh Berpandu

Untuk mencari 42 dalam [5,12,20,42,70], binary search membandingkan item tengah 20, memilih separuh kanan, kemudian menemui 42. Linear search memerlukan empat perbandingan.

teks

BINARY SEARCH\nlow = 0, high = n-1\nULANG selagi low <= high\n  mid = (low + high) DIV 2\n  banding sasaran dengan data[mid]\nTAMAT ULANG

⚠️ AMARAN: Kesilapan lazim: binary search pada senarai tidak tersusun boleh menghapuskan bahagian yang sebenarnya mengandungi sasaran.

🧪 Aktiviti Aplikasi

Jejak satu pusingan bubble sort bagi [7,3,5,1]. Catat setiap perbandingan dan pertukaran.

Rancang jawapan
Laksanakan langkah
Semak hasil dan jelaskan sebab

🧠 Semak Kendiri: Bilakah linear search lebih sesuai daripada binary search?

Jawapan: Apabila data kecil atau belum diisih dan kos mengisih data melebihi manfaat carian binary.

Penerangan Mendalam

🎯 Standard Pembelajaran

3.1.1 Menerangkan dan menggunakan algoritma linear search.
3.1.2 Menerangkan dan menggunakan algoritma binary search.
3.1.3 Menerangkan dan menggunakan algoritma bubble sort.
3.1.4 Menulis pseudokod dan melukis carta alir bagi algoritma carian dan isihan.
3.1.5 Membandingkan kecekapan algoritma carian dan isihan.

💡 RUJUKAN: Buku Teks ASK Tingkatan 3, Bab 3 Algoritma (3.1 Pembangunan Algoritma — linear search, binary search, bubble sort)

Gambaran Keseluruhan

Carian (search) mencari kedudukan sesuatu item dalam senarai, manakala isihan (sort) menyusun item mengikut urutan menaik atau menurun. Buku teks memperkenalkan dua algoritma carian iaitu linear search dan binary search, serta algoritma isihan bubble sort. Pemilihan algoritma bergantung pada sama ada data telah tersusun dan berapa besar saiz data.

Linear search

Linear search menyemak setiap item satu demi satu dari kedudukan pertama sehingga item yang dicari ditemui atau senarai tamat. Ia berfungsi pada senarai yang tersusun mahupun tidak tersusun. Kes terbaik ialah satu perbandingan apabila item berada di kedudukan pertama, dan kes terburuk ialah n perbandingan bagi senarai n item.

Binary search

Binary search hanya boleh digunakan pada senarai yang telah tersusun. Ia membandingkan item tengah dengan sasaran, kemudian membuang separuh senarai yang tidak mungkin mengandungi sasaran. Proses diulang pada separuh yang tinggal sehingga item ditemui atau julat carian kosong.

Kecekapan carian

Linear search memerlukan sehingga n perbandingan, manakala binary search memerlukan hanya kira-kira log₂n perbandingan. Bagi senarai 1000 item, linear search mungkin memerlukan 1000 perbandingan tetapi binary search hanya memerlukan kira-kira 10. Namun binary search memerlukan kos mengisih data terlebih dahulu.

Bubble sort

Bubble sort membandingkan dua item bersebelahan dan menukar kedudukannya jika susunannya salah. Bagi isihan menaik, item yang lebih besar ditukar ke kanan. Selepas setiap pusingan lengkap, item terbesar akan berada di kedudukan akhir yang betul, seperti buih naik ke permukaan.

Pusingan dan perbandingan bubble sort

Bagi senarai n item, bubble sort memerlukan sehingga n−1 pusingan. Pada pusingan ke-i, hanya n−i perbandingan diperlukan kerana item di hujung sudah tersusun. Jika tiada pertukaran berlaku dalam satu pusingan, senarai sudah tersusun dan proses boleh dihentikan lebih awal.

Isihan menaik dan menurun

Isihan menaik menyusun dari nilai terkecil ke terbesar, manakala isihan menurun sebaliknya. Perbezaan dalam kod hanyalah operator perbandingan: gunakan > untuk isihan menaik dan < untuk isihan menurun dalam syarat pertukaran.

Memilih algoritma yang sesuai

Gunakan linear search untuk senarai kecil atau tidak tersusun. Gunakan binary search untuk senarai besar yang telah tersusun dan kerap dicari. Bubble sort mudah difahami dan sesuai untuk pembelajaran serta senarai kecil, tetapi tidak cekap untuk data yang besar.

Glosari Istilah

📚 Glosari mini

Carian (search): Proses mencari kedudukan sesuatu item dalam senarai.
Isihan (sort): Proses menyusun item mengikut urutan tertentu.
Linear search: Carian yang menyemak setiap item satu demi satu dari permulaan.
Binary search: Carian yang membahagi dua senarai tersusun secara berulang.
Bubble sort: Isihan yang membandingkan dan menukar item bersebelahan.
Pusingan (pass): Satu putaran lengkap perbandingan melalui senarai.
Item tengah: Item di kedudukan pertengahan julat carian binary search.
Isihan menaik: Susunan dari nilai terkecil kepada terbesar.
Kecekapan algoritma: Ukuran bilangan operasi yang diperlukan berbanding saiz data.

Indeks tengah binary search = (permulaan + akhir) ÷ 2

Setiap perbandingan binary search membuang separuh daripada julat carian yang tinggal.

Contoh: Senarai 16 item memerlukan paling banyak 5 perbandingan kerana 16 → 8 → 4 → 2 → 1.

🎯 TIP: Jangan hafal istilah Algoritma Search dan Sort secara terasing. Terangkan sebab, syarat penggunaan dan kesannya terhadap output.

Contoh Berpandu dan Amali

Kajian Kes Berpandu

Senarai [15, 11, 14] hendak diisih menaik menggunakan bubble sort. Pusingan pertama: bandingkan 15 dan 11 — kerana 15 lebih besar, ia ditukar menjadi [11, 15, 14]; kemudian bandingkan 15 dan 14 — ditukar menjadi [11, 14, 15]. Pusingan kedua: bandingkan 11 dan 14 — tiada pertukaran; senarai kekal [11, 14, 15]. Kerana tiada pertukaran berlaku dalam pusingan kedua, senarai telah tersusun sepenuhnya. Output akhir ialah 11, 14, 15.

🪜 Kaedah kerja yang boleh diikuti

1Semak sama ada senarai telah tersusun atau belum.
2Pilih linear search jika tidak tersusun, atau binary search jika tersusun.
3Bagi binary search, kira indeks tengah dengan (permulaan + akhir) / 2.
4Bandingkan item tengah dengan sasaran dan buang separuh yang tidak relevan.
5Bagi isihan, bandingkan item bersebelahan dan tukar jika susunan salah.
6Ulang sehingga tiada pertukaran berlaku, kemudian sahkan hasil isihan.

Perwakilan atau contoh teknikal

python

# Bubble sort menaik
def bubble_sort(senarai):
    n = len(senarai)
    for i in range(n):
        for j in range(n - i - 1):
            if senarai[j] > senarai[j + 1]:
                senarai[j], senarai[j + 1] = senarai[j + 1], senarai[j]
    return senarai

print(bubble_sort([15, 11, 14]))   # [11, 14, 15]

Contoh tambahan

python

# Linear search dan binary search
def linear_search(senarai, sasaran):
    for i in range(len(senarai)):
        if senarai[i] == sasaran:
            return i
    return -1

def binary_search(senarai, sasaran):   # senarai mesti tersusun
    mula, akhir = 0, len(senarai) - 1
    while mula <= akhir:
        tengah = (mula + akhir) // 2
        if senarai[tengah] == sasaran:
            return tengah
        elif senarai[tengah] < sasaran:
            mula = tengah + 1
        else:
            akhir = tengah - 1
    return -1

Indeks tengah binary search = (permulaan + akhir) ÷ 2

Setiap perbandingan binary search membuang separuh daripada julat carian yang tinggal.

Contoh: Senarai 16 item memerlukan paling banyak 5 perbandingan kerana 16 → 8 → 4 → 2 → 1.

🧪 Makmal Mini: Algoritma Search dan Sort

Pilih satu masalah sekolah yang berkaitan dengan Algoritma Search dan Sort. Hasilkan penyelesaian lengkap dan jelaskan setiap keputusan yang anda buat.

Nyatakan input, hasil yang dikehendaki dan kekangan.
Gunakan kaedah kerja di atas langkah demi langkah.
Rekod hasil setiap langkah supaya boleh disemak semula.
Uji sekurang-kurangnya tiga kes: biasa, sempadan dan tidak sah.
Tulis refleksi tentang satu penambahbaikan yang boleh dibuat.

🧠 Semak Kendiri: Apakah bukti bahawa penyelesaian bagi Algoritma Search dan Sort berfungsi?

Jawapan: Bukti mesti menunjukkan input, proses, output dijangka, output sebenar dan alasan bahawa semua syarat penting telah diuji.

Rujukan Pantas dan Jadual Fakta

Rujukan Pantas

Bahagian ini merangkumkan fakta Algoritma Search dan Sort yang paling kerap diuji. Gunakannya untuk ulang kaji pantas sebelum peperiksaan, bukan sebagai ganti kepada nota penuh.

Perkara	Butiran
Syarat binary search	Senarai mesti telah tersusun.
Syarat linear search	Tiada; berfungsi pada senarai tersusun atau tidak.
Kes terburuk linear search	n perbandingan bagi n item.
Kes terburuk binary search	Kira-kira log₂n perbandingan.
Bilangan pusingan maksimum bubble sort	n − 1 pusingan.
Perbandingan pada pusingan ke-i	n − i perbandingan.
Operator bagi isihan menaik	> dalam syarat pertukaran.
Kedudukan item terbesar selepas pusingan pertama	Di hujung senarai.

Linear search berbanding binary search

Aspek	Linear search	Binary search
Syarat data	Tidak perlu tersusun	Mesti tersusun
Cara kerja	Semak satu demi satu dari permulaan	Bahagi dua secara berulang
Kes terburuk	n perbandingan	Kira-kira log₂n perbandingan
Sesuai untuk	Senarai kecil atau tidak tersusun	Senarai besar yang telah tersusun

Istilah dan maksud dalam penyelesaian

Istilah	Maksud
Carian (search)	Proses mencari kedudukan sesuatu item dalam senarai.
Isihan (sort)	Proses menyusun item mengikut urutan tertentu.
Linear search	Carian yang menyemak setiap item satu demi satu dari permulaan.
Binary search	Carian yang membahagi dua senarai tersusun secara berulang.
Bubble sort	Isihan yang membandingkan dan menukar item bersebelahan.
Pusingan (pass)	Satu putaran lengkap perbandingan melalui senarai.
Item tengah	Item di kedudukan pertengahan julat carian binary search.
Isihan menaik	Susunan dari nilai terkecil kepada terbesar.
Kecekapan algoritma	Ukuran bilangan operasi yang diperlukan berbanding saiz data.

Kata kunci yang wajib muncul dalam jawapan

Carian (search)
Isihan (sort)
Linear search
Binary search
Bubble sort
Pusingan (pass)

Teknik Menjawab Peperiksaan

Teknik Menjawab Bergaya Peperiksaan

Soalan Sains Komputer menilai ketepatan istilah dan kelengkapan isi. Bagi topik Algoritma Search dan Sort, markah lazimnya diberikan mengikut bilangan isi yang betul, jadi bilangan isi dalam jawapan perlu sepadan dengan bilangan markah yang diperuntukkan.

Membaca kata tugas

Nyatakan atau Namakan — beri jawapan ringkas tanpa huraian panjang.
Terangkan atau Huraikan — beri pernyataan diikuti sebab atau kesan.
Bandingkan — sebut aspek yang sama, kemudian nyatakan kedua-dua pihak bagi setiap aspek.
Hitung — tunjukkan langkah pengiraan kerana markah proses turut diberikan.
Lakar atau Tulis kod — ikut simbol dan sintaks piawai; kesilapan sintaks menyebabkan markah ditolak.

Contoh Soalan dan Jawapan Model

Soalan 1 [2 markah]

Segmen atur cara menggunakan dua gelung bersarang dan menukar nilai no[j] dengan no[j+1] apabila no[j] lebih besar. Nyatakan teori isihan bagi segmen atur cara tersebut dan berikan justifikasi.

🧠 Semak Kendiri: Jawapan model

Jawapan: Teori isihan: isihan buih (bubble sort). Justifikasi: proses isihan membandingkan dua nombor yang bersebelahan dan menukarkan kedudukannya jika nombor di hadapan lebih besar daripada nombor selepasnya.

🎯 TIP: Namakan algoritma dan jelaskan cirinya yang khusus iaitu perbandingan item bersebelahan.

Soalan 2 [1 markah]

Senarai no = [15, 11, 14] diisih menggunakan bubble sort menaik. Nyatakan output yang dijana.

🧠 Semak Kendiri: Jawapan model

Jawapan: 11, 14, 15

🎯 TIP: Jejaki setiap pertukaran pusingan demi pusingan sebelum menulis jawapan.

Soalan 3 [4 markah]

Terangkan perbezaan antara linear search dengan binary search dari segi syarat data dan kecekapan.

🧠 Semak Kendiri: Jawapan model

Jawapan: Linear search boleh digunakan pada senarai yang tersusun atau tidak tersusun, dan memerlukan sehingga n perbandingan bagi senarai n item. Binary search pula memerlukan senarai yang telah tersusun, tetapi hanya memerlukan kira-kira log₂n perbandingan kerana separuh senarai dibuang pada setiap perbandingan.

🎯 TIP: Sentuh kedua-dua aspek yang diminta soalan iaitu syarat data dan kecekapan, bagi kedua-dua algoritma.

Soalan 4 [3 markah]

Senarai tersusun [2, 5, 8, 12, 16, 23, 38, 56] dicari menggunakan binary search untuk nilai 23. Nyatakan bilangan perbandingan yang diperlukan.

🧠 Semak Kendiri: Jawapan model

Jawapan: Perbandingan 1: tengah = 12 (indeks 3), 23 > 12 jadi cari separuh kanan. Perbandingan 2: tengah = 23 (indeks 5), padan. Jumlah 2 perbandingan.

🎯 TIP: Tunjukkan nilai tengah pada setiap langkah, bukan sekadar menulis jumlah perbandingan.

Semakan akhir sebelum menyerahkan jawapan

Bilangan isi sepadan dengan bilangan markah.
Istilah teknikal dieja dan digunakan dengan betul.
Pengiraan menunjukkan langkah dan unit yang lengkap.
Kod atau carta alir menggunakan simbol dan sintaks piawai.
Setiap laluan atau kes yang diminta soalan telah dijawab.

Pengukuhan, KBAT dan Semak Kendiri

Salah Faham yang Perlu Dielakkan

Salah faham	Pembetulan
Binary search boleh digunakan pada senarai yang tidak tersusun.	Binary search hanya sah pada senarai yang telah tersusun.
Bubble sort menukar item yang berjauhan dalam senarai.	Bubble sort hanya membandingkan dan menukar item yang bersebelahan.
Linear search sentiasa lebih perlahan daripada binary search.	Jika item berada di kedudukan pertama, linear search hanya memerlukan satu perbandingan.
Bubble sort memerlukan n pusingan bagi n item.	Bubble sort memerlukan paling banyak n − 1 pusingan.
Selepas satu pusingan bubble sort, senarai sudah tersusun sepenuhnya.	Selepas satu pusingan, hanya satu item iaitu yang terbesar berada pada kedudukan akhir yang betul.
Isihan menaik dan menurun memerlukan algoritma yang berbeza sepenuhnya.	Perbezaannya hanya pada operator perbandingan dalam syarat pertukaran.

⚠️ AMARAN: Dalam jawapan penerangan, menulis definisi sahaja belum mencukupi. Kaitkan konsep Algoritma Search dan Sort dengan situasi, langkah dan akibat.

Strategi Menjawab Soalan

Kerangka jawapan lengkap

Kenal pasti kata tugas seperti nyatakan, terangkan, bandingkan, analisis atau reka.
Gunakan istilah tepat daripada glosari dan berikan konteks.
Tunjukkan langkah, pengiraan, jadual kesanan atau bukti jika berkaitan.
Nyatakan sebab pemilihan serta kelemahan alternatif.
Semak unit, syarat sempadan, sintaks dan kesimpulan.

✍️ Latihan Pengukuhan dan KBAT

Terangkan Carian (search) menggunakan ayat sendiri dan satu contoh baharu.
Bandingkan Isihan (sort) dengan Linear search.
Gunakan kaedah kerja untuk menyelesaikan satu situasi baharu berkaitan Algoritma Search dan Sort.
Analisis salah faham berikut dan betulkan: Binary search boleh digunakan pada senarai yang tidak tersusun.
Cipta satu kes ujian yang boleh mendedahkan kesilapan dalam Algoritma Search dan Sort.
Nilai penyelesaian anda dari sudut ketepatan, kejelasan, kecekapan dan keselamatan.

Semak Kendiri

🧠 Semak Kendiri: Betulkan pernyataan: Binary search boleh digunakan pada senarai yang tidak tersusun.

Jawapan: Binary search hanya sah pada senarai yang telah tersusun.

🧠 Semak Kendiri: Betulkan pernyataan: Bubble sort menukar item yang berjauhan dalam senarai.

Jawapan: Bubble sort hanya membandingkan dan menukar item yang bersebelahan.

🧠 Semak Kendiri: Betulkan pernyataan: Linear search sentiasa lebih perlahan daripada binary search.

Jawapan: Jika item berada di kedudukan pertama, linear search hanya memerlukan satu perbandingan.

🧠 Semak Kendiri: Betulkan pernyataan: Bubble sort memerlukan n pusingan bagi n item.

Jawapan: Bubble sort memerlukan paling banyak n − 1 pusingan.

🧠 Semak Kendiri: Algoritma carian yang menyemak setiap item satu demi satu dipanggil ___.

Jawapan: Linear search — Linear search berfungsi pada senarai tersusun mahupun tidak.

🧠 Semak Kendiri: Algoritma carian yang memerlukan senarai tersusun ialah ___.

Jawapan: Binary search — Binary search membuang separuh julat carian pada setiap perbandingan.

🧠 Semak Kendiri: Algoritma isihan yang membandingkan dua item bersebelahan dipanggil ___.

Jawapan: Bubble sort — Bubble sort juga dikenali sebagai isihan buih.

Uji kefahaman anda 🎯

Daftar percuma untuk jawab kuiz topik ini, tanya AI Tutor, dan kumpul XP.

Daftar Percuma