インプレースソートアルゴリズムのガイドはJava実装で機能します

投稿日: 2019-10-18 2022-10-29
タグ: Algorithms, Java, sorting

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）になることに注意してください。

この図は、前の場合よりも必要なステップが少ないことを示しています。

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

これは私たちが望んでいたことを実行しますが、十分に効率的ではありません。 で操作するアレイが2つあるため、 にはO（n）個の余分なスペースが必要です。その上、新しいアレイの作成と削除は通常、遅い操作です。

プロセスの図を見てみましょう。

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. 例

インプレースアプローチを使用している多くのソートアルゴリズムがあります。それらのいくつかは、挿入ソート、バブルソート、ヒープソート、クイックソート、およびシェルソートであり、それらについてさらに学び、Java実装をチェックアウトすることができます。

また、コムソートとヒープソートについても言及する必要があります。これらはすべてスペースが複雑ですO（log n）。

Big-O表記法の詳細や、アルゴリズムの複雑さに関する実用的なJavaの例を確認することも役立ちます。

6. 結論

この記事では、いわゆるインプレースアルゴリズムについて説明し、擬似コードといくつかの例を使用してそれらがどのように機能するかを示し、この原則に基づいて機能するいくつかのアルゴリズムをリストし、最後にJavaで基本的な例を実装しました。

いつものように、コード全体はGitHubのにあります。

getdocs

13036