GCSEではバイナリサーチとマージソートはどのように機能するのか

GCSEのコンピュータサイエンスのアルゴリズムを復習しているなら、4つの名前が何度も出てきます。線形探索、バイナリサーチ、バブルソート、マージソートです。試験委員会は、これらをトレースさせたり、実行時間を指摘させたり、疑似コードの欠落行を埋めさせるのが好きです。ここに、試験およびそれ以上で実際に重要なものがあります。

線形探索：基本

線形探索はリスト内のすべての項目を1つずつチェックして、ターゲットを見つけるか終わりに達するまで続けます。それだけです。

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)で、大規模なデータセットではこのため劇的に高速です。100万個の項目のソート済みリストを検索する場合、線形探索は最大100万回の比較が必要ですが、バイナリサーチは約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²)です。各要素について、ほぼ全体のリストをもう一度スキャンする必要があります。大規模なデータが遅いため、実際のソフトウェアではほぼ使用されませんが、試験官はそれを好みます。手作業でのトレースは実行可能で、反復パスとスワップの考えを明確に示しているからです。トレーステーブルで比較とスワップの数を数える方法を知っています。これは一般的なマークスキームの項目です。

マージソート：分割と征服

マージソートはリストを繰り返し半分に分割し、各サブリストに1つの項目が含まれるまで、次にそれらのサブリストをソート順で再度マージします。

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の用語で時間複雑度を述べるか、少なくともそれを言葉で説明します。