Як працюють двійковий пошук і сортування злиттям для GCSE?

Якщо ви повторюєте алгоритми для GCSE Computer Science, чотири назви постійно з'являються: лінійний пошук, двійковий пошук, сортування бульбашкою та сортування злиттям. Екзаменаційні комісії люблять просити вас трасувати ці алгоритми вручну, визначати часову складність або заповнювати пропущені рядки псевдокоду. Ось що насправді важливо для екзамену та за його межами.

Лінійний пошук: базовий рівень

Лінійний пошук перевіряє кожен елемент у списку один за одним, доки не знайде цільовий елемент або не дійде до кінця. От і все.

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

У найгіршому випадку ви перевіряєте кожен елемент, тому це O(n). У найкращому випадку цільовий елемент перший, тому O(1). Екзаменатори люблять просити вас назвати обидва. Лінійний пошук працює з невідсортованими даними, що є його однією справжньою перевагою над двійковим пошуком.

Двійковий пошук: алгоритм, на якому люди помиляються

Двійковий пошук працює тільки з відсортованим списком. Ви порівнюєте цільовий елемент із серединним елементом. Якщо цільовий елемент менший, ви відкидаєте верхню половину; якщо більший, відкидаєте нижню половину. Повторюєте, доки не знайдете або не скінчаться елементи.

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

Це O(log n), тому він набагато швидший на великих наборах даних. Шукаючи в відсортованому списку з мільйона елементів, лінійний пошук може потребувати до мільйона порівнянь; двійковий пошук потребує близько 20. Екзаменатори часто дають вам список, скажімо, 16 чисел і просять вас трасувати, які індекси перевіряються — практикуйтесь із ручкою та папером, а не тільки в голові.

Сортування бульбашкою: просте, але повільне

Сортування бульбашкою повторно проходить список, міняючи місцями сусідні елементи, якщо вони в неправильному порядку. Кожен повний прохід переміщує найбільший несортований елемент на його правильну позицію в кінці.

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])

У найгіршому випадку це O(n²) — для кожного елемента ви можете майже весь список скануватиповторно. Його рідко використовують у реальному програмному забезпеченні, тому що він повільний на великих даних, але екзаменаторам він подобається, тому що його трасування вручну можна впоратися, і він чітко показує ідею повторних проходів і обмінів. Знайте, як підрахувати кількість порівнянь і обмінів у таблиці трасування; це поширений пункт схеми оцінювання.

Сортування злиттям: розділи та владарюй

Сортування злиттям розділяє список навпіл повторно, доки кожен підсписок не матиме один елемент, потім об'єднує ці підсписки назад у відсортованому порядку.

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)

Крок злиття порівнює перші елементи кожної половини і вибирає менший, повторюючи, доки обидві половини не будуть використані. Це дає O(n log n), що легко перемагає сортування бульбашкою на всьому, крім крихітних списків. Питання GCSE іноді просять вас намалювати діаграму розділення та злиття — форму дерева, яка показує список, що розділяється вниз, а потім повторно об'єднується. Практикуйтесь малювати це для списку з 8 чисел, щоб ви були швидкими під час екзамену.

Що насправді тестують екзаменатори

Більшість схем оцінювання хочуть, щоб ви могли:

• Трасувати алгоритм крок за кроком і записувати стан списку після кожного проходу або порівняння.
• Вказати часову складність в нотації Big O або принаймні описати її словами.