【C言語】降順になるように挿入ソートで並び替える方法

2023年9月10日

この記事では、C言語の挿入ソートアルゴリズムを使って、降順に並び替える方法を解説します。

初心者の方でもわかりやすく、サンプルコードと実行結果の例を交えて説明します。

目次から探す

降順に並び替えるためのアルゴリズム

通常の挿入ソートのアルゴリズム

挿入ソートは、配列を前から順番に見ていき、各要素を適切な位置に挿入していくアルゴリズムです。

具体的な手順は以下の通りです。

配列の2番目の要素から順番に処理を行います。
現在の要素を、それより前の要素と比較します。
現在の要素が前の要素より小さい場合、前の要素を1つ後ろにずらします。
現在の要素が前の要素より大きい場合、現在の要素をその位置に挿入します。

降順に並び替えるための変更点

通常の挿入ソートでは、要素を比較する際に「現在の要素が前の要素より小さいかどうか」を判定します。

しかし、降順に並び替える場合は「現在の要素が前の要素より大きいかどうか」を判定する必要があります。

そのため、比較の条件を変更する必要があります。

降順に並び替えるためのコード例

コードの概要

以下のコードは、降順に並び替えるための挿入ソートのコード例です。

#include <stdio.h>
void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] < key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    insertionSort(arr, n);
    
    printf("降順に並び替えた結果：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

降順に並び替えた結果：9 8 5 2 1

コードの解説

insertionSort関数は、挿入ソートを行うための関数です。

引数として配列と要素数を受け取ります。

iを1から始めて、配列の要素を順番に処理していきます。
keyに現在の要素を代入し、jにiの1つ前の値を代入します。
jが0以上であり、arr[j]がkeyより小さい場合、arr[j]を1つ後ろにずらします。
jが0未満またはarr[j]がkeyより大きい場合、keyをその位置に挿入します。
main関数では、降順に並び替えたい配列を定義し、insertionSort関数を呼び出します。
並び替えた結果を表示します。

また、コード例では配列の要素数を固定していますが、実際のプログラムでは動的に要素数を取得するなどの工夫が必要です。