Algoritma Search dan Sort

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.

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.

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

Gambaran Keseluruhan

Algoritma carian mencari kedudukan sasaran, manakala algoritma isihan menyusun data mengikut aturan. Pemilihan algoritma bergantung pada saiz, susunan awal, kos penyediaan dan kekerapan operasi. Murid perlu menjejak setiap perbandingan dan pertukaran.

Linear search

Linear search menyemak item satu demi satu dari awal hingga sasaran ditemui atau data habis. Ia berfungsi pada data tidak tersusun dan mudah dilaksana. Dalam kes terburuk, semua item perlu diperiksa, tetapi bagi data kecil kosnya mungkin lebih rendah daripada mengisih dahulu.

Binary search

Binary search membandingkan sasaran dengan item tengah dan membuang separuh ruang carian setiap langkah. Data mesti telah diisih. Sempadan low dan high perlu bergerak melepasi mid; jika tidak, julat mungkin tidak mengecil dan gelung tidak tamat.

Bubble sort

Bubble sort membandingkan pasangan bersebelahan dan menukar pasangan yang salah urutan. Selepas satu laluan, satu nilai ekstrem berada pada kedudukan akhir. Penanda swapped boleh menghentikan algoritma lebih awal apabila tiada pertukaran berlaku.

Bucket sort dan pemilihan

Bucket sort mengagihkan nilai kepada bekas berdasarkan julat, mengisih dalam bekas dan menggabungkannya. Ia sesuai apabila julat serta taburan diketahui. Penggunaan memori dan kaedah mengendalikan nilai negatif atau sempadan bekas perlu dirancang.

Kajian Kes Berpandu

Cari 42 dalam [5,12,20,42,70]. Linear search membuat empat perbandingan. Binary search membanding 20, kemudian memilih separuh kanan dan menemui 42. Jika data belum diisih dan carian hanya sekali, kos mengisih mungkin tidak berbaloi.

Perwakilan atau contoh teknikal

low = 0, high = n - 1
ULANG SELAGI low <= high
  mid = (low + high) DIV 2
  JIKA data[mid] = sasaran: JUMPA
  JIKA data[mid] < sasaran: low = mid + 1
  JIKA TIDAK: high = mid - 1
TAMAT ULANG

Salah Faham yang Perlu Dielakkan

Strategi Menjawab Soalan