C언어로 배열이 정렬되어 있는지 확인하는 프로그램 (재귀 및 반복문)

n개의 요소로 구성된 배열 arr[]가 주어졌을 때, 우리의 과제는 이 배열이 정렬된 순서인지 아닌지를 판별하는 것입니다. 배열이 정렬되어 있다면 "배열은 정렬된 순서입니다"를 출력하고, 그렇지 않다면 "배열은 정렬된 순서가 아닙니다"를 출력하면 됩니다.

이 문제는 재귀(Recursion) 방식 또는 반복문(Iteration) 방식으로 해결할 수 있으며, 이 글에서는 두 가지 방법을 모두 살펴보겠습니다.

재귀 접근 방식

재귀 접근 방식이란 무엇일까요? 재귀 방식에서는 원하는 결과를 얻을 때까지 함수를 계속해서 다시 호출합니다. 이때 함수가 반환하는 값들은 스택(stack) 메모리에 저장됩니다.

입력

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

출력

배열은 정렬된 순서입니다

설명 − 12 < 13 < 14 < 16 < 18 이므로 배열은 오름차순으로 정렬되어 있습니다.

입력

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

출력

배열은 정렬된 순서가 아닙니다

설명 − 2가 1보다 작지 않으므로(즉, 앞 요소가 뒤 요소보다 크므로) 배열은 정렬되어 있지 않습니다.

문제 해결 접근 방법

• 배열 arr[]를 입력받고, 변수 n에 배열의 크기를 초기화합니다.

• 배열의 시작 지점까지 도달했다면 true(1)를 반환합니다.

• 현재 요소 바로 앞의 요소가 더 크다면(순서가 어긋났다면) false(0)를 반환합니다.

• n을 하나 감소시키고 2번 단계로 돌아갑니다.

알고리즘

Start
In function int arraySortedCheck(int arr[], int n)
    Step 1→ 만약 n == 1 또는 n == 0 이라면,
        Return 1
    Step 2→ 만약 arr[n-1] < arr[n-2] 라면,
        Return 0
    Step 3→ Return arraySortedCheck(arr, n-1)
In Function int main(int argc, char const *argv[])
    Step 1→ arr[]를 {12, 13, 14, 16, 18}로 선언 및 초기화
    Step 2→ int n을 sizeof(arr)/sizeof(arr[0])로 선언 및 초기화
    Step 3→ 만약 arraySortedCheck(arr, n)이라면,
        "배열은 정렬된 순서입니다" 출력
    Step 4→ Else
        "배열은 정렬된 순서가 아닙니다" 출력
Stop

예제 코드

// 재귀 방식
#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[] = {12, 13, 14, 16, 18};
    int n = sizeof(arr)/sizeof(arr[0]);
    if(arraySortedCheck(arr, n)){
        printf("배열은 정렬된 순서입니다\n");
    }
    else
        printf("배열은 정렬된 순서가 아닙니다\n");
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

배열은 정렬된 순서입니다

반복문 접근 방식

반복문 방식에서는 for문, while문, do-while문 같은 루프를 사용하여 조건이 참(1)인 동안 명령문을 반복 실행합니다.

입력

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

출력

배열은 정렬된 순서입니다

설명 − 12 < 13 < 14 < 16 < 18 이므로 배열은 정렬된 순서입니다.

입력

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

출력

배열은 정렬된 순서가 아닙니다

설명 − 2가 1보다 작지 않으므로 배열은 정렬되어 있지 않습니다.

문제 해결 접근 방법

• 배열 arr[]를 입력받습니다.

• 배열의 끝에 도달할 때까지 반복문을 수행합니다.

  • 현재 요소가 다음 요소보다 크면 false(0)를 반환하고 종료합니다.

  • 그렇지 않으면 계속 진행합니다.

• 모든 요소를 통과하면 true(1)를 반환합니다.

알고리즘

Start
In function int arraySortedCheck(int arr[], int n)
    Step 1→ For i = 0 이고 i < n-1 이고 ++i 로 반복
        만약 arr[i] > arr[i+1] 이라면,
            Return 0
    Step 2→ Return 1
In Function int main(int argc, char const *argv[])
    Step 1→ arr[]를 {12, 13, 14, 16, 18}로 선언 및 초기화
    Step 2→ int n을 sizeof(arr)/sizeof(arr[0])로 선언 및 초기화
    Step 3→ 만약 arraySortedCheck(arr, n)이라면,
        "배열은 정렬된 순서입니다" 출력
    Step 4→ Else
        "배열은 정렬된 순서가 아닙니다" 출력
Stop

예제 코드

// 반복문 방식
#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[] = {12, 13, 14, 16, 18};
    int n = sizeof(arr)/sizeof(arr[0]);
    if(arraySortedCheck(arr, n)){
        printf("배열은 정렬된 순서입니다\n");
    }
    else
        printf("배열은 정렬된 순서가 아닙니다\n");
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

배열은 정렬된 순서입니다