3-10. 挿入法を使った降順整列のアルゴリズム

2025年2月20日 14:39

　本記事では挿入法を使って降順に整列するアルゴリズムの問題演習をします。

問題　挿入法を使って、降順に整列するためのアルゴリズムを作成してください。

解答

n ← データ数
i ← 2
while (i ≦ n)
　j ← 1
　while (A[i] ≦ A[j] and i ＞ j )
　　j ← j + 1
　endwhile
　if ( A[ i ] ＞ A [ j ])
　　w ← A [ i ]
　　k ← i - 1
　　while (k ≧ j)
　　　A[k+1] ← A[k]
　　　k ← k - 1
　　endwhile
　　A [ j ]　← w
　endif
　i ← i + 1
endwhile

※降順ですから、「前の値＞挿入する値＞次の値」という順になることに注意してください。

解説

挿入法を使った降順ソートのアルゴリズム解説

1. 問題の整理

　「挿入法（Insertion Sort）」を用いて、与えられた配列を降順（大きい順）に並べ替えるアルゴリズムを作成します。

2. 与えられた擬似コードの整理

(1) 変数の意味

n：データの個数（配列 A の要素数）
i：ソート処理の対象となる要素のインデックス（2番目の要素から処理を開始）
j：挿入位置を見つけるためのインデックス
w：現在ソート対象の値を一時的に保持する変数
k：要素を右にシフトするためのインデックス

(2) アルゴリズムの流れ

i を 2 から n まで順に進め、A[i]（現在の要素）を適切な位置に挿入する。
j を 1 から i-1 まで動かし、A[i] をどこに挿入するかを探す。
- A[j] が A[i] 以上の間 j を増やすことで、A[i] が挿入されるべき位置 j を決める。
挿入位置が決まったら、A[i] より小さい要素を右へずらす。
A[j] に A[i] を格納する。

3. 修正後の擬似コード

擬似言語の文法に合わせて、より分かりやすい形に書き直す。

手続き 降順挿入ソート(配列 A, 整数 n)
  i ← 2  // 2番目の要素から開始

  while (i ≦ n) do
    j ← 1

    // 挿入位置を探す
    while (A[i] ≦ A[j] and i ＞ j) do
      j ← j + 1
    endwhile

    // 挿入が必要な場合
    if (A[i] ＞ A[j]) then
      w ← A[i]  // 挿入する値を一時保存
      k ← i - 1

      // 要素を右にシフト
      while (k ≧ j) do
        A[k+1] ← A[k]
        k ← k - 1
      endwhile

      // 適切な位置に挿入
      A[j] ← w
    endif

    i ← i + 1
  endwhile
手続き終了

4. 実際の動作をシミュレーション

例：入力

A = [5, 2, 9, 3, 7]

Step 1 (i=2, A[i]=9)

j を探す (A[i] = 9 を適切な位置に移動)
A[1] = 5 < 9 → j = 1
9 を A[1] に挿入
結果 [9, 5, 2, 3, 7]

Step 2 (i=3, A[i]=3)

j を探す (A[i] = 3)
A[2] = 2 < 3 → j = 2
3 を A[2] に挿入
結果 [9, 5, 3, 2, 7]

Step 3 (i=4, A[i]=7)

j を探す (A[i] = 7)
A[1] = 9 > 7 → j = 2
7 を A[2] に挿入
結果 [9, 7, 5, 3, 2]

最終的な結果

A = [9, 7, 5, 3, 2]

降順ソート完了。

5. 計算量と特徴

最良ケース（すでに降順）：O(n)
最悪ケース（昇順で並んでいる）：O(n^2)
平均時間計算量：O(n^2)

このアルゴリズムは 小規模データに適したシンプルなソート手法 です。

6. まとめ

降順に並べるための挿入ソート を解説
擬似コードを整理し、修正
アルゴリズムの手順を詳細に説明
シミュレーションで動作確認
計算量や特徴を解説

補足
Java とPythonで実装

1. Javaによる実装

public class InsertionSortDescending {
    public static void insertionSortDescending(int[] A) {
        int n = A.length;

        for (int i = 1; i < n; i++) {
            int w = A[i];  // 挿入する値を一時保存
            int j = i - 1;

            // w（A[i]）より小さい要素を右にシフト
            while (j >= 0 && A[j] < w) {
                A[j + 1] = A[j];
                j--;
            }

            // 適切な位置に挿入
            A[j + 1] = w;
        }
    }

    public static void main(String[] args) {
        int[] A = {5, 2, 9, 3, 7};
        insertionSortDescending(A);

        // 結果を表示
        System.out.print("Sorted Array (Descending): ");
        for (int num : A) {
            System.out.print(num + " ");
        }
    }
}

説明

i = 1 から n-1 までループを回す。
A[i] を適切な位置に挿入するため、j を使って探索。
A[j] < A[i] の間、右にシフト。
適切な位置 (A[j+1]) に A[i] を挿入。

出力

Sorted Array (Descending): 9 7 5 3 2

2. Pythonによる実装

def insertion_sort_descending(A):
    n = len(A)
    
    for i in range(1, n):
        w = A[i]  # 挿入する値を一時保存
        j = i - 1

        # w（A[i]）より小さい要素を右にシフト
        while j >= 0 and A[j] < w:
            A[j + 1] = A[j]
            j -= 1
        
        # 適切な位置に挿入
        A[j + 1] = w

# 動作確認
A = [5, 2, 9, 3, 7]
insertion_sort_descending(A)
print("Sorted Array (Descending):", A)

説明

for i in range(1, n) で 2 番目の要素から順に処理。
while j >= 0 and A[j] < w で、A[i] より小さい要素を右にシフト。
A[j+1] = w で適切な位置に A[i] を挿入。

出力

Sorted Array (Descending): [9, 7, 5, 3, 2]

以上です。