C言語で配列がソート済みかどうかを判定するプログラム（再帰・反復の両アプローチを解説）

要素数 n の配列 arr[] が与えられたとき、その配列がソート済み（昇順）であるかどうかを判定するのが本記事のテーマです。ソート済みであれば「The array is in sorted order」を出力し、そうでなければ「The array is not in sorted order」を出力します。

この問題は再帰と反復（ループ）という2つのアプローチで解くことができます。ここでは、それぞれの方法を順番に詳しく解説していきます。

再帰によるアプローチ

再帰とは、求める結果が得られるまで関数自身を繰り返し呼び出す手法のことです。再帰を用いる場合、関数が返す値はスタックメモリに保存されるという特徴があります。

入出力例

入力

arr[] = {12, 13, 14, 16, 18}

出力

The array is in sorted order

解説 − 12 < 13 < 14 < 16 < 18 となっているため、配列は昇順にソートされています。

入力

arr[] = {2, 1, 3, 5, 6}

出力

The array is not in sorted order

解説 − 先頭の 2 の次に 1 が来ており順序が崩れているため、ソートされた状態ではありません。

問題を解くための考え方

• 配列 arr[] を入力として受け取り、n に配列のサイズを設定します。
• 配列の先頭まで調べ終えたら、true を返します。
• 隣り合う要素の順序が崩れていたら（前の要素より後ろの要素が小さい場合）、false を返します。
• n を 1 減らして、手順 2 に戻ります。

アルゴリズム

開始
関数 int arraySortedCheck(int arr[], int n) 内
    ステップ1 → n == 1 または n == 0 ならば、
        1 を返す
    ステップ2 → arr[n-1] < arr[n-2] ならば、
        0 を返す
    ステップ3 → arraySortedCheck(arr, n-1) を返す
関数 int main(int argc, char const *argv[]) 内
    ステップ1 → arr[] を {1,8,3,4,7} で宣言・初期化
    ステップ2 → int n を sizeof(arr)/sizeof(arr[0]) で宣言・初期化
    ステップ3 → arraySortedCheck(arr, n) が真ならば、
        "Array is in sorted order" を出力
    ステップ4 → そうでなければ、
        "Array is not in sorted order" を出力
終了

実装例

// 再帰によるアプローチ
#include <stdio.h>
// ソート済みかどうかを判定する再帰関数
int arraySortedCheck(int arr[], int n){
    // すべての要素をチェックし終え、
    // すべて整列していた場合
    if (n == 1 || n == 0)
        return 1;
    // 配列がソートされていない場合
    if(arr[n-1] < arr[n-2])
        return 0;
    return arraySortedCheck(arr, n-1);
}
int main(int argc, char const *argv[]){
    int arr[] = {1,8,3,4,7};
    int n = sizeof(arr)/sizeof(arr[0]);
    if(arraySortedCheck(arr, n)){
        printf("Array is in sorted order\n");
    }
    else
        printf("Array is not in sorted order\n");
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

Array is in sorted order

反復（ループ）によるアプローチ

反復によるアプローチでは、for 文や while 文、do-while 文などのループ構文を使い、条件が真（1）である限り処理を繰り返し実行します。

入出力例

入力

arr[] = {12, 13, 14, 16, 18}

出力

The array is in sorted order

解説 − 12 < 13 < 14 < 16 < 18 となっているため、配列は昇順にソートされています。

入力

arr[] = {2, 1, 3, 5, 6}

出力

The array is not in sorted order

解説 − 2 の後に 1 が続いており順序が崩れているため、ソートされた状態ではありません。

問題を解くための考え方

• 配列 arr[] を入力として受け取ります。
• 配列の末尾に達するまでループを回します。
  • 現在の要素が次の要素より大きい場合は、false を返して終了します。
  • そうでなければ、そのまま処理を続けます。
• 手順 2 を繰り返します。

アルゴリズム

開始
関数 int arraySortedCheck(int arr[], int n) 内
    ステップ1 → i = 0 から i < n-1 まで ++i でループ
        arr[i] > arr[i+1] ならば、
            0 を返す
    ステップ2 → 1 を返す
関数 int main(int argc, char const *argv[]) 内
    ステップ1 → arr[] を {1,8,3,4,7} で宣言・初期化
    ステップ2 → int n を sizeof(arr)/sizeof(arr[0]) で宣言・初期化
    ステップ3 → arraySortedCheck(arr, n) が真ならば、
        "Array is in sorted order" を出力
    ステップ4 → そうでなければ、
        "Array is not in sorted order" を出力
終了

実装例

// 反復（ループ）によるアプローチ
#include <stdio.h>
int arraySortedCheck(int arr[], int n){
    for (int i = 0; i < n-1; ++i){
        // 隣接する要素の順序が崩れている場合
        if(arr[i] > arr[i+1])
            return 0;
    }
    // すべての要素をチェックし終え、
    // すべて整列していた場合
    return 1;
}
int main(int argc, char const *argv[]){
    int arr[] = {1,8,3,4,7};
    int n = sizeof(arr)/sizeof(arr[0]);
    if(arraySortedCheck(arr, n)){
        printf("Array is in sorted order\n");
    }
    else
        printf("Array is not in sorted order\n");
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

Array is in sorted order

まとめ

どちらのアプローチも計算量は O(n) で同じですが、再帰版は関数呼び出しごとにスタックフレームが必要となるため、非常に大きな配列ではスタックオーバーフローのリスクがあります。一方、反復版は追加のメモリをほとんど消費せずに済むため、実務では反復処理が選ばれることが多くなっています。用途に応じて適切な手法を選びましょう。