이진 검색과 병합 정렬은 GCSE에서 어떻게 작동하나?

GCSE 컴퓨터 과학 알고리즘을 복습 중이라면 계속 나오는 네 가지 이름이 있습니다: 선형 검색, 이진 검색, 버블 정렬, 병합 정렬. 시험 기관은 이들을 손으로 추적하고, 실행 시간을 찾아내거나, 빠진 의사코드 줄을 채우도록 묻는 것을 좋아합니다. 시험과 그 이후를 위해 실제로 중요한 것이 무엇인지 여기 있습니다.

선형 검색: 기본

선형 검색은 목표를 찾거나 끝에 도달할 때까지 리스트의 모든 항목을 하나씩 확인합니다. 그게 전부입니다.

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 용어로 시간 복잡도를 명시하거나, 최소한 말로 설명하세요 (