Python マージソートチュートリアル

データのソートは、データプラクティショナーが日常業務で行う最も一般的な操作の1つです。多くの場合、意味のある情報を抽出するためにデータを特定の順序で表示する必要があります。幸いなことに、今日ではこの作業を手動で行う必要はありません。コンピューターが私たちのために驚異的なパフォーマンスで魔法をかけてくれます。

データをソートするためのいくつかの戦略があります。このチュートリアルでは、最も効果的なソート手法の1つを分析します。 “マージソート”アルゴリズムは、未整列の配列を最初により小さな配列に分割し、後で正しい順序でマージすることでソートする分割統治戦略を使用します。

次のセクションでは、マージソートアルゴリズムのすべての詳細、Pythonでの見た目、スムーズな実装のための実用的なヒントについて説明します。

マージソートとは何ですか？

多くのソートアルゴリズムが存在しますが、マージソートよりも優れたパフォーマンスを発揮するものを見つけるのは難しいです。このアルゴリズムは、大規模なデータベースのソートや通常のコンピューター上のファイルの整理など、あらゆる種類の実世界アプリケーションで使用されています。

このアルゴリズムは分割統治パラダイムに基づいており、次の3つの部分に分解できます：

• 分割：このプロセスは問題をより小さな部分問題に分割します。
• 征服：部分問題は再帰的に解決されます。
• 結合：部分問題の解決策は結合され、最終的な解決策が達成されます。

分割統治戦略

マージソートの仕組みを見てみましょう。 マージソートアルゴリズムを適用して、次の数字を順序付けたいとします。 このアルゴリズムは、データを再帰的に二つの部分に分割し、それぞれのリストが1つの要素になるまで分割を続けます。 その後、それらを組み合わせて別のリストにソートして結合します。

Merge Sort Problem. Source: DataCamp

マージソートの時間複雑度と空間複雑度

特定の問題に最適なソートアルゴリズムは事前にわかることはできません。 アルゴリズム以外にも、コードを書くために使用されるプログラミング言語、実行されるハードウェア、およびソートされるデータの特性など、複数の変数を考慮する必要があります。

ソートアルゴリズムの正確な実行時間を予測することはできませんが、時間複雑度と空間複雑度を分析することで、さまざまなソートアルゴリズムのパフォーマンスを比較することができます。

マージソートの時間複雑度

私たちが ビッグO記法と時間計算量 に関する別のガイドで説明したように、時間計算量分析の目的はアルゴリズムの正確な実行時間を予測することではなく、入力データの量が増加するにつれてアルゴリズムの実行時間がどのように変化するかを分析することによって、アルゴリズムの効率性を評価することです。

時間計算量分析はビッグO記法で書かれ、これは関数が成長または減少する速度を表す数学的記法です。マージソートは対数線形または線形対数的な時間計算量を持ち、O(N log(N))と表記されます。ここで、Nはリスト内の要素の数です。’O’という文字は成長の「順序」を表します。

時間計算量分析において、線形対数的複雑性はおおよそ線形複雑性と同様に振る舞い、つまりその実行はデータの量に直接比例します。したがって、データの量が2倍になると、アルゴリズムがデータを処理するのにかかる時間も2倍になるべきです。つまり、分割とマージの回数も2倍になります。

マージソートの時間計算量は線形に振る舞うため、その複雑性は最良ケース、平均ケース、最悪ケースのいずれにおいても同じままです。つまり、入力の順序に関わらず、アルゴリズムが完了するために必要なステップ数は常に同じです。

マージソートの空間計算量

最後に、タスクを完了するために必要な時間に加えて、アルゴリズムの複雑性を分析する際のもう一つの重要な側面は、問題が大きくなるにつれてアルゴリズムが完了するために必要なメモリの量を推定することです。

この概念は、空間計算量と補助空間によってカバーされています。後者は、アルゴリズムが使用する余分なスペースまたは一時スペースを指し、前者は入力サイズに関連してアルゴリズムが占有する総スペースを指します。つまり、空間計算量には補助空間と入力によって使用されるスペースの両方が含まれます。

マージソートの空間計算量はO(N)です。これは、ソートされた入力配列の半分をマージするためにサイズNの補助配列を使用するためです。補助配列はマージされた結果を格納するために使用され、入力配列はソートされた結果で上書きされます。

Pythonにおけるマージソートの実装

Pythonでマージソートアルゴリズムを実装しましょう。アルゴリズムをコード化するいくつかの方法がありますが、再帰に基づいた方法を採用し、他のイテレーションに基づく代替手段よりも理解しやすく、コード行数が少なくて済む方法を選択します。

マージソートにおける再帰の理解

このトピックが初めての場合、プログラミングでは、再帰が発生すると、関数が自分自身を呼び出します。強力なこれらの関数について詳しく学ぶには、Pythonの再帰関数の理解チュートリアルをご覧ください。

マージソートを実装するには、まず基本ケースを定義します: もしリストに1つの要素しかない場合、それはすでにソートされているので、直ちに返します。そうでない場合は、リストを2つの半分、left_halfとright_halfに分割し、それぞれに再帰的にmerge_sort()を呼び出します。このプロセスは、すべてのサブリストが1つの要素を含むまで続きます。

これらのソートされたサブリストができたら、マージプロセスを開始します。これには、3つのインデックス変数を初期化します: iはleft_half内の位置を追跡するため、jはright_half内の位置を追跡し、kは最終的なマージされたリストの位置を示します。それから両方の半分から要素を比較します。現在のleft_half内の要素が小さい場合は、それをmy_list[k]に配置してiを前に進めます。それ以外の場合は、right_halfから要素を取り、my_list[k]に配置してjを増やします。比較ごとに、kを最終リスト内の次の位置に進めます。

このプロセスは、どちらかの半分のすべての要素を比較するまで続きます。もしleft_halfまたはright_halfに要素が残っている場合は、それらを直接最終リストに追加し、データが残らないようにします。マージソートは再帰的に動作するため、このマージプロセスは、リスト全体がソートされるまで再帰の各レベルで実行されます。

Python実装

以下は、前の図の並び替えられていないリストを使用したコードの例です:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge Sortと他のソートアルゴリズム

Mergeソートは非常に高速なソートアルゴリズムであり、特に大規模なデータベースに適しており、他のアルゴリズムのベンチマークとしてよく使用されます。ただし、短いリストの場合、そのパフォーマンスは他のソートアルゴリズムよりも低くなる傾向があります。

以下の表では、Mergeソートと他の人気のあるソートアルゴリズムを比較できます。

Merge Sortの実用的な応用

マージソートは、大きなリストをソートする際に高いパフォーマンスを発揮しますが、小さなリストを扱う場合は効率が低下します。同様に、入力リストに一定の順序がすでにある場合、マージソートはリストの順序に関わらず同じ手順を実行するため、効率が低下します。

マージソートが特に便利なユースケースは、リンクリストです。リンクリストは、互いにリンクされたノードの連結から構成されるデータ構造です。各ノードにはデータが含まれ、次のノードとの接続を行うリンクがあります。

リンクリストにはマージソートが適しているのは、データへの連続アクセスのみが必要であり、これはリンクリストの性質によく合っています。また、マージソートは安定なソーティングアルゴリズムであり（つまり、ソートされた出力の中で等しい要素の相対的な順序を維持します）、これはリンクリストの順序を維持する上で非常に重要な考慮事項です。

一般的なエラーとトラブルシューティング

マージソートアルゴリズムは非常にわかりやすく、コードの改善余地は限られています。ただし、入力データのサイズを考慮することで、ソーティング戦略の複雑さを増すことができます。

すでに述べたように、マージソートは大きなデータセットとの相性が良いです。小さなデータセットの場合、挿入ソートなどのO(N^2)の時間複雑度を持つ他のソーティングアルゴリズムの方が適しているかもしれません。その場合、単純に挿入ソートアルゴリズムを選択するサイズの閾値を設定するだけで、マージソートの代わりに挿入ソートアルゴリズムを選択することができます。

それ以外に、探索するのに良いアイデアは並列化です。マージソートの手順は、適切な計算能力を持っていれば簡単に並列化することができ、それにより完了時間を短縮することができます。詳細については、CPU vs GPU ガイドをご覧ください。

結論

マージソートは、最も効果的で人気のあるソートアルゴリズムの1つですが、アルゴリズムの素晴らしく広がり続ける宇宙の中で学ぶべきことはまだまだたくさんあります。アルゴリズムの技術的な側面、動作方法、およびそれに伴う複雑さ、利点、欠点に興味がある場合は、これらの DataCamp のリソースを活用して学習を続けることができます：

• データ構造とアルゴリズムコース
• Python プログラミングスキルトラック
• Python データ基礎スキルトラック
• 中級 Python コース
• Python でのデータアナリストキャリアトラック
• ビッグO表記と時間計算量