3-7. 選択法を使った降順整列のアルゴリズム　選択法の変法

　本記事では、選択法の降順整列の場合のアルゴリズムについて問題演習します。

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

解答

i ← 1
n ← データ数
while (i ＜ n)
　j ← i + 1
　while (j ≦ n)
　　if (A[i] ＜ A[j] )
　　　w ← A[j]
　　　A[j] ← A[i]
　　　A[i] ← w
　　endif
　　j ← j + 1
　endwhile
　i ← j + 1
endwhile

　最大値を選択するように、A[i] ＜ A[j] という条件に変更します。

補足
Java とPython で実装

　選択ソート（Selection Sort）を使って降順にソートする Java と Python のコードを作成しました。

---

Java版

import java.util.Arrays;

public class SelectionSortDescending {
    public static void main(String[] args) {
        int[] A = {5, 2, 9, 1, 5, 6};
        selectionSortDescending(A);
        System.out.println(Arrays.toString(A));
    }

    public static void selectionSortDescending(int[] A) {
        int n = A.length;
        for (int i = 0; i < n - 1; i++) {
            int maxIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (A[j] > A[maxIndex]) { // 大きい要素を探す
                    maxIndex = j;
                }
            }
            // 交換
            int temp = A[i];
            A[i] = A[maxIndex];
            A[maxIndex] = temp;
        }
    }
}

---

Python版

def selection_sort_descending(A):
    n = len(A)
    for i in range(n - 1):
        max_index = i
        for j in range(i + 1, n):
            if A[j] > A[max_index]:  # 大きい要素を探す
                max_index = j
        # 交換
        A[i], A[max_index] = A[max_index], A[i]

A = [5, 2, 9, 1, 5, 6]
selection_sort_descending(A)
print(A)

---

解説

• 選択ソート（Selection Sort）は、毎回最も大きい値（降順の場合）を見つけて先頭に入れ替える。

• 外側のループ：ソートが完了するまで、各位置に正しい値を配置。

• 内側のループ：現在の範囲内で最大値を探し、先頭と入れ替え。

• 降順にするために if A[j] > A[max_index] という比較を使用。

以上です。