Как работают бинарный поиск и сортировка слиянием для GCSE?

Если вы повторяете алгоритмы для GCSE Computer Science, четыре названия повторяются снова и снова: линейный поиск, бинарный поиск, сортировка пузырьком и сортировка слиянием. Экзаменационные комиссии обожают просить вас трассировать их вручную, определить время выполнения или заполнить пропущенные строки псевдокода. Вот что действительно важно для экзамена и дальше.

Linear search: базовый уровень

Linear search проверяет каждый элемент в списке, один за другим, пока не найдёт целевой элемент или не достигнет конца. Вот и всё.

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

В худшем случае вы проверяете каждый элемент, поэтому это O(n). В лучшем случае целевой элемент стоит первым, так что O(1). Экзаменаторам нравится просить вас указать оба. Linear search работает с неотсортированными данными, что является его единственным реальным преимуществом перед бинарным поиском.

Binary search: то, что сбивает людей с толку

Binary search работает только на отсортированном списке. Вы сравниваете целевой элемент с элементом посередине. Если целевой элемент меньше, вы отбрасываете верхнюю половину; если больше, отбрасываете нижнюю половину. Повторяете, пока не найдёте его или не кончатся элементы.

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), поэтому он драматически быстрее на больших наборах данных. Поиск в отсортированном списке из миллиона элементов может потребовать до миллиона сравнений при linear search; binary search нужно примерно 20. Экзаменаторы часто дают вам список, скажем, из 16 чисел и просят вас трассировать, какие индексы проверяются — практикуйтесь вручную с ручкой и бумагой, не просто в голове.

Bubble sort: простая, но медленная

Bubble sort многократно проходит по списку, меняя местами соседние элементы, если они в неправильном порядке. Каждый полный проход ставит самый большой неотсортированный элемент на его правильную позицию в конце.

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²) — для каждого элемента вы можете сканировать почти весь список заново. Она редко используется в реальном ПО, потому что медленная на больших данных, но экзаменаторам она нравится, потому что трассировку вручную можно управлять и она чётко показывает идею повторных проходов и обменов. Знайте, как считать количество сравнений и обменов в таблице трассировки; это частый пункт в схеме оценки.

Merge sort: разделяй и властвуй

Merge sort многократно делит список пополам, пока каждый подсписок не будет содержать один элемент, затем объединяет эти подсписки обратно в отсортированном порядке.

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)

Шаг merge сравнивает первые элементы каждой половины и выбирает меньший, повторяя, пока обе половины не будут исчерпаны. Это даёт O(n log n), что комфортно бьёт bubble sort на всём, кроме крошечных списков. Вопросы GCSE иногда просят вас нарисовать диаграмму разделения и объединения — форму дерева, показывающую список, делящийся вниз и затем рекомбинирующийся. Практикуйтесь рисовать это для списка из 8 чисел, чтобы вы были быстры в условиях экзамена.

Что экзаменаторы действительно проверяют

Мост схем оценки требуют от вас возможности:

• Трассировать алгоритм пошагово и записывать состояние списка после каждого прохода или сравнения.
• Указать временную сложность в терминах Big O или по крайней мере описать её словами.