[C언어 알고리즘] 2.2.2 순차 정렬 알고리즘 구현

[C언어 알고리즘] 2.2.2 순차 정렬 알고리즘 구현

---

이번에는 순차 정렬 알고리즘을 구현해 보기로 해요.

순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    반복(i:=0->n)

        반복(j:=i+1->n)

            조건(compare(base[i], base[j]) > 0)

                교환(base[i],base[j])

 

이번에는 순차 정렬 알고리즘을 구현하는 예를 보여드릴게요.

//순차 정렬(Sequential Sort)

#include <stdio.h>

먼저 두 개의 정수 값을 교환하는 SWAP 매트로 함수를 작성합니다.

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환

 

이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요. 원소 형식에 관계없이 정렬하는 방법은 디딤돌 정렬 알고리즘 (C언어)를 참고하세요.

 

void SequenceSort(int *base, int n);

int main(void)

{

    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };

    SequenceSort(arr, 10);

    return 0;

}

 

그리고 여기에서는 정렬 알고리즘을 수행하면서 배열의 원소 값을 교환할 때마다 콘솔 화면에 출력하도록 합시다. 실제 정렬 알고리즘에서는 정렬 과정에서 출력하는 부분을 정의할 필요는 없습니다. 따라서 여기에서 작성하는 ViewArr 함수를 주석 처리를 하면 정렬 알고리즘을 구현한 함수로 볼 수 있습니다.

void ViewArr(int *arr, int n);

void SequenceSort(int *base, int n)

{

    int i, j;

    ViewArr(base, n);//현재 상태 출력

순차 정렬은 이중 반복문을 사용합니다. 외부 반복문은 0에서 n까지 순차적으로 이동합니다.

    for (i = 0; i<n; i++)

    {

내부 반복문에서는 인덱스 i 뒤쪽 요소들 중에 인덱스 i보다 작은 값이 있으면 인덱스 i번째 요소와 교환하는 것을 반복합니다. 이를 통해 인덱스 i에서 마지막 원소 중에 제일 작은 값을 인덱스 i로 이동할 수 있습니다.

        for (j = i+1; j<n; j++)

        {

인덱스 i 와 인덱스 j요소의 값을 비교하여 i번째 요소가 더 크면 두 개의 값을 교환합니다.

            if (base[i]>base[j])//i번째 원소가 더 크면

            {

                SWAP(base[i], base[j]);//교환

여기에서는 값을 변경할 때마다 결과를 화면에 출력하기 위해 ViewArr 함수를 호출하고 있습니다. 실제 정렬 알고리즘에서 이 함수는 필요가 없습니다. 따라서 실제 정렬 알고리즘을 구현할 때 ViewArr 함수 호출 부분은 주석 처리하세요.

                ViewArr(base, n);//상태 출력

            }

        }

    }

}

 

테스트 목적으로 배열의 내용을 출력하는 함수입니다.

void ViewArr(int *arr, int n)

{

    int i = 0;

인덱스 0에서 마지막 요소까지 값을 출력합니다.

    for (i = 0; i<n; i++)

    {

        printf("%2d ", arr[i]);

    }

전체 요소 값을 출력한 후에 개행 문자를 출력합니다.

    printf("\n");

}

[그림 2.2] 순차 정렬 알고리즘 실행 결과