1. 序章

このチュートリアルでは、内部ソートと外部ソートの違いについて説明します。

2. 内部ソートと外部ソートの違い

データの並べ替えプロセスが完全にコンピュータのランダムアクセスメモリ（RAM）内で行われる場合、これは内部並べ替えと呼ばれます。 これは、ソートされるデータセットのサイズがRAMに保持できるほど小さい場合はいつでも可能です。

より大きなデータセットを並べ替える場合、すべてがRAMに収まらないため、一度にメモリに保持する必要があるのはデータの小さなチャンクだけです。 残りのデータは通常、ハードディスクなどのより大きな、しかし低速のメディアに保持されます。 これらの大規模なデータセットの並べ替えには、外部並べ替えと呼ばれるさまざまなアルゴリズムのセットが必要になります。

3. 内部ソートに使用されるアルゴリズム

以下は、内部ソートに使用できるいくつかのアルゴリズムです。

3.1. バブルソート：

これは、リストを繰り返しステップ実行する単純な並べ替えアルゴリズムであり、隣接する要素を比較し、順序が間違っている場合はそれらを交換します。 詳細については、別の記事をご覧ください。

アルゴリズムは、リストがソートされるまでリストをループします。

3.2. 挿入ソート：

この並べ替えアルゴリズムは、トランプを並べ替える方法と同じように機能します。 データセットは実質的に並べ替えられた部分と並べ替えられていない部分に分割されます、次にアルゴリズムは並べ替えられていない部分から要素を取得し、以下に示すように並べ替えられた部分の正しい位置に配置します。

詳細については、の記事をご覧ください。

3.3. クイックソート：

この並べ替えアルゴリズムはピボット要素を取得し、データセットを2つのサブ配列に分割します。一方のサブ配列は要素より大きく、もう一方のサブ配列は要素より小さくなります。 データセットが次のように並べ替えられるまで、同じプロセスがサブ配列に対して繰り返されます。

詳細については、の記事を確認してください。 これらすべてのアルゴリズムのスペースcomplexityはO（）です。これは、スペース要件がデータセットのサイズとともに増加することを意味します。

4. 外部ソーティングに使用されるアルゴリズム

外部ソートには、データセットのサイズに応じてスペースの複雑さが増さないアルゴリズムが必要です。 マージソートのスペースの複雑さはO（）ですが、O（）に最適化できます。

4.1. データフロー図

次の図は、8GBのRAMとマージソートアルゴリズムを備えたコンピューターを使用して50GBの大規模なデータセットをソートするための高レベルのデータフローを示しています。

次の手順が含まれています。

  • コンピューターのRAMは8GBであるため、大きなデータセットを8GB未満のサイズの小さなサブセットに分割します。 このステップのスペースの複雑さは、データセットのサイズに応じて増加しないため、O（）です。
  • 一般的な内部ソートアルゴリズムのいずれかを使用して、サブセットを一度に1バッチソートします。 これらのアルゴリズムの複雑さの空間はO（）です。 これらのサブセットのサイズは8GB未満であり、それらをソートするには同じ量のメモリが必要になります。
  • ポインタを使用して、ソートされたサブセットをマージすることを繰り返します。 この間、現在のポインターの要素の値をサブセットと比較し、最小値を出力リストに入れます。 次に、ポインタをサブセットの最小値を持つ次の項目に移動します。 ポインターを使用するため、このステップのスペースの複雑さはO（）であり、データセットのサイズに応じて増加することはありません。

4.2. 例を使用したステップバイステップ

この方法を使用して、次の例を処理します。

ASORTINGANDMERGINGEXA MPLE

コンピューターは10個の要素を格納できると想定しています。

最初のステップは、データセットを3つのサブセットに分割し、それらを外部ディスクにロードすることです。

  • ASORTINGAN
  • DMERGINGEX
  • 十分な

次に、ステップ2の一部として、次のようにします。

  • 1 st サブセット（ ASORTINGAN ）をコンピューターのRAMにロードし、（ AAGINNORST ）にソートします。 次に、それを外部ディスクに保存します。
  • 2 nd サブセット（ DMERGINGEX ）をコンピューターのRAMにロードし、（ DEEGGIMN R X ）にソートします。 次に、それを外部ディスクに保存します。
  • 3 rd サブセット（ AMPLE ）をコンピューターのRAMにロードし、（ AELMP ）にソートします。 次に、それを外部ディスクに保存します。

そして、最後に：

3つのポインター（各入力サブセットに1つ）と出力用に1つを初期化します。 1 st サブセット、2 nd サブセット、および3 rdサブセットのポインターは1です。 また、出力データセットのポインターは1です。

  • コンピューターRAMへの3つのソートされたデータセットへのポインターによって示されるように要素をロードします。 3つのサブセットがあるため、最大3つの要素がロードされます。 （ ADA ）をコンピュータのRAMにロードします。
  • これらの要素から最小値を見つけて、出力ポインターで識別される場所にある出力配列にロードします。 Aは（ ADA ）で最も低いため、Aをロードして外部ディスクに出力します。
  • 出力ポインターを1増やし、最も低い要素を持つデータセットのポインターも1増やします。 したがって、1 st サブセットへのポインターを2に増やし、出力データセットを2に増やす必要があります。 2 ndデータセットおよび3rdデータセットへのポインターは1のままです。
  • b、c、およびdで概説されている手順を繰り返します。 これで、1 st サブセット、2 nd サブセット、および3 rd サブセットのポインターがそれぞれ2,1,1であるため、ロードされます（ ADA ）外部ディスクからRAMへ。 （ ADA ）の最小値はAであり、出力データセットの2 nd要素として格納されます。 ポインターの値は再び増加し、2回目の反復後の3つのサブセットのポインターの値はそれぞれ2、1、2になり、出力のポインターは3になります。
  • これらの手順は、3つのサブセットのすべての要素が処理されるまで続きます。 すべての要素が処理された後、出力は次のようになります。

AAADEEEGGGIILMMNNNOPR RSTX

5. 結論

要約すると、データセットがコンピューターのRAM内に収まるほど比較的小さい場合は内部ソートを使用し、データセットが大きく、スペースの複雑さが最小のアルゴリズムを使用する場合は外部ソートを使用します。