インプレースソートアルゴリズムの仕組み

1. 前書き

このチュートリアルでは、インプレースソートアルゴリズムの仕組みを説明します。

2. インプレースアルゴリズム

*インプレースアルゴリズムは、入力データを変換するために補助データ構造を必要としないアルゴリズムです。*基本的に、アルゴリズムは入力操作に余分なスペースを使用しないことを意味します。 実際には、入力を出力でオーバーライドします。
ただし、実際には、アルゴリズムでは、補助変数用に小さくて一定でない追加のスペースが実際に必要になる場合があります。 *ほとんどの場合、このスペースの複雑さは_O(log n)_ですが、場合によっては線形以外のものも許可されます。*

3. 疑似コード

擬似コードを見て、インプレースアルゴリズムとアウトオブプレースアルゴリズムを比較してみましょう。
_n_個の数字の配列を逆にしたいと仮定します。

3.1. インプレースアルゴリズム

問題について考えると、出力として入力配列と反転配列があることがわかります。 最終的に、元の配列は実際には必要なく、逆の配列のみが必要です。
次に、値をまったく新しい配列に移動するのではなく、入力を上書きしないのはなぜですか? これを行うには、現在作業中の値を一時的に保存するために、* 1つの追加変数*のみが必要です。
reversInPlace(array A[n])
    for i from 0 to n/2
    temp = A[i]
    A[i] = A[n - 1 - i]
    A[n - 1 - i] = temp
配列の大きさに関係なく、この場合、必要な追加スペースは常に_O(1)_になることに注意してください。
この図は、前のケースよりも必要なステップが少ないことを示しています。
link:/uploads/Screen-Shot-2019-08-07-at-3.40.33-PM-100x59.png%20100w []

3.2. アウトオブプレースアルゴリズム

一方、これは非常にシンプルで、より明白な方法で行うこともできます。 同じサイズの新しい配列を作成し、元の配列の値を対応する順序でコピーしてから、元の配列を削除できます。
reverseOutOfPlace(array A[n])
    create new array B[n]
    for i from 0 to n - 1
        B[i] = A[i]
    delete A
    return B
これは私たちが望んでいたことを行いますが、十分に効率的ではありません。 * _O(n)_余分なスペースが必要です* *操作する2つの配列があるため*。 それに加えて、新しいアレイの作成と削除は通常、遅い操作です。
プロセスの図を見てみましょう。
link:/uploads/Screen-Shot-2019-08-07-at-3.40.22-PM-100x68.png%20100w []

4. Java実装

ここで、前のセクションで学んだことをJavaで実装する方法を見てみましょう。
まず、インプレースアルゴリズムを実装します。
public static int[] reverseInPlace(int A[]) {
    int n = A.length;
    for (int i = 0; i < n / 2; i++) {
        int temp = A[i];
        A[i] = A[n - 1 - i];
        A[n - 1 - i] = temp;
    }
    return A;
}
これが期待どおりに機能することを簡単にテストできます。
@Test
public void givenArray_whenInPlaceSort_thenReversed() {
    int[] input = {1, 2, 3, 4, 5, 6, 7};
    int[] expected = {7, 6, 5, 4, 3, 2, 1};
    assertArrayEquals("the two arrays are not equal", expected,
      InOutSort.reverseInPlace(input));
}
次に、アウトオブプレースアルゴリズムの実装を確認します。
public static int[] reverseOutOfPlace(int A[]) {
    int n = A.length;
    int[] B = new int[n];
    for (int i = 0; i < n; i++) {
        B[n - i - 1] = A[i];
    }
    return B;
}
テストは非常に簡単です。
@Test
public void givenArray_whenOutOfPlaceSort_thenReversed() {
    int[] input = {1, 2, 3, 4, 5, 6, 7};
    int[] expected = {7, 6, 5, 4, 3, 2, 1};
    assertArrayEquals("the two arrays are not equal", expected,
      InOutSort.reverseOutOfPlace(input));
}

5. 例

インプレースアプローチを使用しているソートアルゴリズムは多数あります。 それらの一部は、https://www.baeldung.com/java-insertion-sort [挿入ソート]、https://www.baeldung.com/java-bubble-sort [バブルソート]、https:// wwwです。 baeldung.com/java-heap-sort[heap sort]、https://www.baeldung.com/java-quicksort [quicksort]、およびlink:/java-shell-sort[shell sort] ]そして、それらについてさらに学び、Java実装をチェックアウトできます。
また、comb sortとheapsortに言及する必要があります。 これらはすべて、スペースの複雑さ_O(log n)_を持っています。
link:/big-o-notation[Big-O Notationの理論]の詳細を調べたり、https://www.baeldung.comを調べたりすることも有用です。 / java-algorithm-complexity [アルゴリズムの複雑さに関する実践的なJavaの例]。

6. 結論

この記事では、いわゆるインプレースアルゴリズムについて説明し、擬似コードといくつかの例を使用してそれらがどのように機能するかを示し、この原理で動作するいくつかのアルゴリズムをリストし、最終的にJavaで基本例を実装しました。
通常どおり、コード全体を見つけることができますhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubで]。