配列がCでソートされているかどうか（反復および再帰）をチェックするプログラム

n個の要素を持つ配列arr[]が与えられた場合、タスクは、指定された配列が並べ替えられた順序であるかどうかを確認することです。並べ替えられた順序である場合は、「配列は並べ替えられた順序です」と出力します。それ以外の場合は、「配列ソートされた順序ではありません」。

上記の問題を解決するために、反復アプローチまたは再帰アプローチを使用できます。両方について説明します。

再帰的アプローチ

では、再帰的アプローチとは何ですか？再帰的アプローチでは、望ましい結果が得られるまで、関数を何度も再帰的に呼び出します。再帰的アプローチでは、関数によって返される値はスタックメモリに格納されます。

入力

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をデクリメントし、ステップ2に進みます。

アルゴリズム

Start
In function int arraySortedCheck(int arr[], int n)
   Step 1→ If n == 1 || n == 0 then,
      Return 1
   Step 2→ If arr[n-1] < arr[n-2] then,
      Return 0
   Step 3→ Return arraySortedCheck(arr, n-1)
In Function int main(int argc, char const *argv[])
   Step 1→ Declare and initialize arr[] as {1,8,3,4,7}
   Step 2→ Declare and initialize int n as sizeof(arr)/sizeof(arr[0])
   Step 3→ If arraySortedCheck(arr, n) then,
      Print "Array is in sorted order”
   Step 4→ Else
      Print "Array is not in sorted order”
Stop

例

//Recursive approach
#include <stdio.h>
//Recursive function to check if it
//is in sorted order or not
int arraySortedCheck(int arr[], int n){
   //all elements are checked and
   //all are in sorted order
   if (n == 1 || n == 0)
      return 1;
   //when an array is not in sorted order
   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に進みます。

アルゴリズム

Start
In function int arraySortedCheck(int arr[], int n)
   Step 1 → Loop For i = 0 and i < n and ++i
      If arr[n-1] < arr[n-2] then,
         Return 0
   Step 2→ Return 1
In Function int main(int argc, char const *argv[])
   Step 1→ Declare and initialize arr[] as {1,8,3,4,7}
   Step 2→ Declare and initialize int n as sizeof(arr)/sizeof(arr[0])
   Step 3→ If arraySortedCheck(arr, n) then,
      Print "Array is in sorted order”
   Step 4→ Else
      Print "Array is not in sorted order”
Stop

例

//Iterative approach
#include <stdio.h>
int arraySortedCheck(int arr[], int n){
   for (int i = 0; i < n; ++i){
      //when an array is not in sorted order
      if(arr[n-1] < arr[n-2])
         return 0;
   }
   //all elements are checked and
   //all are in sorted order
   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