アルゴリズムの仕組み
Chapter 3 Sorting Algorithms

第3章: ソーティングアルゴリズム

ソーティングは、オブジェクトの順序を論理的に並べ替えるプロセスです。例えば、クレジットカードの請求書は日付順に取引を表示し、本棚の本は著者名とタイトルのアルファベット順に並べられています。ソーティングは、コンピューターサイエンスの基本的な操作であり、多くのアプリケーションで重要な役割を果たします。この問題に取り組むさまざまな古典的なソーティングアルゴリズムがあります。

この章では、いくつかの古典的なソーティング手法と、優先度キューと呼ばれる重要なデータ構造について考えます。まず、選択ソート、挿入ソート、シェルソートなどの基本的なソーティング手法について説明します。これらの手法は多くのアプリケーションで適切に使用されますが、大規模な問題では、再帰的なソーティングアルゴリズムであるマージソートとクイックソートを使用します。最後に、ソーティングやその他のアプリケーションでの優先度キューの使用について説明します。

基本的なソート

最も単純なソーティングアルゴリズムは、次の操作を行います:

  • 選択ソート: 最小の要素を見つけて先頭の要素と交換し、次に小さい要素を見つけて2番目の要素と交換するなど。
  • 挿入ソート: 各要素を順番に取り出し、既に考慮された要素の中で適切な位置に挿入する(それらを整列したままにする)。

これらの操作は、人間が通常ソーティングタスクを実行する方法を反映しており、小規模な問題には効果的です。しかし、大規模な配列のソートには適していません。

選択ソート

選択ソートは、次のように動作する単純なソーティングアルゴリズムです: まず、配列の中で最小の要素を見つけ、先頭の要素と交換します(先頭の要素が既に最小の場合は交換しません)。次に、次に小さい要素を見つけ、2番目の要素と交換します。この方法で配列全体がソートされるまで続けます。

選択ソートの内部ループは、Here is the Japanese translation of the provided markdown file, with the code comments translated:

ソート関数は、未ソートのサブ配列 a[i..N-1] の中で最小の要素を見つけるために使用されます。最小の要素のインデックスは min に格納されます。次に、a[i] と a[min] が交換されることで、最小の要素が最終的な位置に置かれます。インデックス i が左から右に移動するにつれて、左側の要素はソート済みの順序になり、二度と触れられることはありません。

Java での選択ソートの実装は以下の通りです:

public static void selectionSort(Comparable[] a) {
    // 配列の長さを取得
    int N = a.length;
    // 配列の先頭から末尾まで繰り返す
    for (int i = 0; i < N; i++) {
        // 最小の要素のインデックスを初期化
        int min = i;
        // 現在の最小の要素より小さい要素があるかを確認
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        // 最小の要素と現在の要素を交換
        exch(a, i, min);
    }
}

選択ソートは、長さ N の配列をソートするのに約 ~N^2/2 回の比較と N 回の交換を行います。入力に依存せずに、順序が整っている配列や全ての要素が等しい配列でも、ランダムに並んでいる配列と同じくらいの時間がかかります。

挿入ソート

挿入ソートは、最終的にソートされた配列を1つずつ構築していく、別の単純なソートアルゴリズムです。クイックソート、ヒープソート、マージソートなどの高度なアルゴリズムに比べると、大きな配列では非効率的ですが、いくつかの利点があります:

  • 小さなデータセットでは効率的です。
  • 実際の使用では選択ソートよりも効率的です。
  • 安定ソートです。つまり、等しいキーを持つ要素の相対的な順序は変わりません。
  • その場で (in-place) ソートできます。つまり、追加のメモリ領域 O(1) しか必要ありません。
  • オンラインソートができます。つまり、受け取り次第にリストをソートできます。

Java での挿入ソートの実装は以下の通りです:

public static void insertionSort(Comparable[] a) {
    // 配列の長さを取得
    int N = a.length;
    // 配列の2番目の要素から最後まで繰り返す
    for (int i = 1; i < N; i++) {
        // 現在の要素より前の要素と比較し、適切な位置に挿入する
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            // 要素を1つ右にずらす
            exch(a, j, j-1);
        }
    }
}

挿入ソートの内部ループでは、より大きな要素を1つ右にずらして、現在の要素を適切な位置に挿入します。挿入ソートの実行時間は、入力アイテムの初期順序に依存します。例えば、配列が大きく、その要素がすでに順序付けられている(または近似的に順序付けられている)場合、挿入ソートはランダムに順序付けられているか逆順の場合に比べて、はるかに高速です。

シェルソート

シェルソートは、挿入ソートの単純な拡張で、配列の要素を遠く離れた位置で交換することで速度を上げ、最終的に挿入ソートで効率的に並べ替えられる部分的に整列した配列を生成します。

アイデアは、配列を再配置して、任意の開始位置から h 番目の要素を取り出すと、ソートされた部分列が得られるという性質を持たせることです。このような配列は h-ソートされていると呼ばれます。別の言い方をすると、h-ソートされた配列は、h 個の独立したソートされた部分列が交互に並んでいるものです。大きな h の値で h-ソートすることで、配列の要素を長距離移動させ、小さな h の値で h-ソートしやすくなります。このようなプロセスを、最終的に h=1 になるような h の値の列で行えば、ソートされた配列が得られます。これがシェルソートです。

以下は、Javaでのシェルソートの実装です:

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        return N == 0;
    }
   
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private boolea
```以下は、提供されたマークダウンファイルの日本語翻訳です。コードの部分は翻訳せず、コメントのみ翻訳しています。
 
```java
n less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
 
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

このコードは、配列 pq を使ってヒープ順序付けされた完全二分木を表現するマックス指向のバイナリヒープを実装しています。insert() と delMax() の操作は、swim() と sink() のヘルパーメソッドを使ってヒープ順序を維持します。親が子より大きい場合や子が親より大きい場合に、キーを交換することでヒープ順序を復元します。

ストップウォッチ

より有用な抽象データ型は、ストップウォッチの簡単で効果的な抽象化です。これは対向ページに示されています。使用するには、タイマーを開始したい時にストップウォッチオブジェクトを作成し、elapsedTime() メソッドを使ってオブジェクト作成からの経過時間を秒単位で取得できます。実装では、Java の System.currentTimeMillis() を使って1970年1月1日午前0時からの現在時刻をミリ秒単位で取得しています。

インスタンス変数 start にはストップウォッチが作成された時間が記録され、elapsedTime() ではこの start を使って経過時間を計算します。クライアントコードの例は典型的なものです。計算を行い、ストップウォッチを使ってその計算にかかった時間を計測しています。ストップウォッチデータ型は、ストップウォッチの概念(インターフェース)と実装(Java の System.currentTimeMillis() の使用)を分離しているため、優れた抽象化となっています。このインターフェースと実装の分離は、本書で紹介するすべての抽象データ型の基本的な特徴です。

まとめ

抽象データ型は、オブジェクト指向プログラミングにおいて不可欠な要素であり、現代のプログラミングで広く使用されています。このセクションでは以下のことを学びました:

  • Javaクラスとして抽象データ型を定義し、データ型の値を定義するインスタンス変数とそれらの値に対する操作を実装するインスタンスメソッドを持つ。
  • 同じAPIに対して、異なる表現を使った複数の実装を開発する。
  • 抽象データ型の概念と実装を分離することで、優れた抽象化を実現する。データ型
  • APIと、クライアント、抽象データ型の実装を区別する。
  • 抽象データ型のAPIを設計する。
  • テストやデバッグに使用するクライアントとテストクライアントを開発する。
  • アサーションを使用して、抽象データ型の実装の正しさを推論する。
  • 同じAPIの異なる実装の性能を比較する。

これらの活動は、Javaプログラムの開発の不可欠な部分です。私たちが書くすべてのJavaプログラムには、ライブラリからの抽象データ型が使用されます。多くのプログラムでは、新しい抽象データ型の開発も行われます。次のセクションでは、多くのプログラムの重要なコンポーネントである3つの基本的な抽象データ型について考え、1.4節では、実装の性能特性を詳細に分析するプロセスについて検討します。

Chapter 2 Algorithms FundamentalsChapter 4 Searching Algorithms