Bagaimana binary search dan merge sort bekerja untuk GCSE?

Jika Anda merevisi algoritma untuk GCSE Computer Science, empat nama muncul berulang kali: linear search, binary search, bubble sort, dan merge sort. Badan ujian senang meminta Anda melacak ini secara manual, menentukan runtime, atau mengisi baris pseudocode yang hilang. Inilah apa yang benar-benar penting untuk ujian dan seterusnya.

Linear search: baseline

Linear search memeriksa setiap item dalam list, satu demi satu, hingga menemukan target atau mencapai akhir. Itu saja.

for i = 0 to length(list) - 1
    if list[i] == target then
        return i
return -1

Kasus terburuk, Anda memeriksa setiap elemen, jadi O(n). Kasus terbaik, target ada di awal, jadi O(1). Penguji senang meminta Anda menyatakan keduanya. Linear search bekerja pada data yang tidak disortir, yang merupakan satu-satunya keuntungan nyatanya dibanding binary search.

Binary search: yang membingungkan orang

Binary search hanya bekerja pada list yang disortir. Anda membandingkan target dengan item tengah. Jika target lebih kecil, Anda buang separuh atas; jika lebih besar, buang separuh bawah. Ulangi hingga menemukan atau kehabisan item.

low = 0
high = length(list) - 1
while low <= high
    mid = (low + high) / 2
    if list[mid] == target then
        return mid
    else if list[mid] < target then
        low = mid + 1
    else
        high = mid - 1
return -1

Ini O(log n), itulah mengapa jauh lebih cepat pada dataset besar. Cari list tersortir dengan satu juta item dan linear search mungkin butuh hingga satu juta perbandingan; binary search butuh sekitar 20. Penguji umum memberi Anda list, katakan, 16 angka dan meminta Anda melacak indeks mana yang diperiksa — praktikkan ini secara manual dengan pena dan kertas, bukan hanya di kepala Anda.

Bubble sort: sederhana tapi lambat

Bubble sort secara berulang berjalan melalui list, menukar item yang berdekatan jika dalam urutan salah. Setiap pass penuh mendorong item unsorted terbesar ke posisi yang benar di akhir.

for i = 0 to length(list) - 1
    for j = 0 to length(list) - 2 - i
        if list[j] > list[j+1] then
            swap(list[j], list[j+1])

Kasus terburuk adalah O(n²) — untuk setiap elemen, Anda mungkin pindai hampir seluruh list lagi. Jarang digunakan dalam software nyata karena lambat pada data besar, tetapi penguji menyukainya karena melacaknya secara manual dapat dikelola dan jelas menunjukkan ide pass dan swap berulang. Ketahui cara menghitung jumlah perbandingan dan swap dalam tabel pelacakan; itu item skema mark umum.

Merge sort: bagi dan taklukkan

Merge sort membagi list menjadi dua bagian secara berulang hingga setiap sublist memiliki satu item, lalu menggabungkan sublist itu kembali dalam urutan tersortir.

function mergeSort(list)
    if length(list) <= 1 then
        return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

Langkah merge membandingkan item depan setiap bagian dan memilih yang lebih kecil, mengulangi hingga kedua bagian selesai. Ini memberikan O(n log n), yang mengalahkan bubble sort dengan nyaman pada apapun kecuali list kecil. Pertanyaan GCSE kadang meminta Anda menggambar diagram bagi-dan-gabung — bentuk pohon yang menunjukkan list membagi ke bawah lalu bergabung kembali. Praktikkan menggambar ini untuk list 8 angka sehingga Anda cepat saat ujian.

Apa yang benar-benar diuji penguji

Sebagian besar skema mark menginginkan Anda mampu:

• Melacak algoritma langkah demi langkah dan menulis keadaan list setelah setiap pass atau perbandingan.
• Menyatakan kompleksitas waktu dalam istilah Big O, atau setidaknya mendeskripsikannya dengan kata-kata (