n개의 요소가 있는 배열 arr[]이 주어졌을 때 우리의 임무는 주어진 배열이 정렬된 순서인지 아닌지를 확인하는 것입니다. 정렬된 순서이면 "배열이 정렬된 순서대로"를 인쇄하고, 그렇지 않으면 "배열 정렬된 순서가 아닙니다.
위에서 언급한 문제를 해결하기 위해 Iterative 또는 Recursive 접근 방식을 사용할 수 있습니다. 둘 다 논의할 것입니다.
재귀적 접근
그렇다면 재귀 접근 방식은 무엇입니까? 재귀 접근 방식에서는 원하는 결과를 얻을 때까지 함수를 계속해서 재귀적으로 호출합니다. 재귀적 접근에서 함수에 의해 반환된 값은 스택 메모리에 저장됩니다.
입력
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-loop, while-loop 또는 do-while 루프와 같은 루프를 사용하여 조건이 1을 의미하는 true가 될 때까지 명령문을 실행합니다.
입력
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