[C언어 소스] 순차 정렬(Sequential Sort) 알고리즘

이번에는 반복적인 방법으로 해결하는 순차 정렬(Sequential Sort) 알고리즘을 살펴볼게요.

정렬 알고리즘은 배열의 자료를 원하는 순으로 배치하는 알고리즘을 말해요. 정렬 알고리즘은 입력 인자로 정렬할 자료들이 있는 배열의 시작 주소와 원소 개수, 비교 알고리즘이 필요합니다. 그리고 수행 후에는 배열 내의 자료들은 원하는 순서로 배치한 상태여야 합니다.

순차 정렬은 맨 앞에서부터 제일 작은 원소를 배치하게 만들어 나가는 알고리즘이예요. 이를 위해 배치할 자리에 있는 원소를 뒤쪽에 있는 원소들과 비교하면서 작은 것을 발견하면 배치할 위치의 원소와 교환해요.

알고리즘

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

반복(i:=0->n)

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

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

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

순차 정렬 알고리즘 실행 화면

점근식 계산

이번에는 수행 속도를 점근식 표기 방식으로 계산해 보아요.

내부 반복문을 수행하는 시간을 S(i, n)이라고 하면 n-i 번 비교하고 교환 횟수는 최악일 때 n-i번이예요. 따라서 S(i, n) <= n-i(비교횟수) + n-2(최악의 교환 횟수) = 2(n-i)

외부 반복문은 i가 0~n-1까지 변하면서 내부 반복문을 수행합니다. 따라서 외부 반복문을 수행하는데 걸리는 시간을 T(n)이라고 하면 S(0,n)+S(1,n)+…+S(n-1,n)입니다.

T(n) = S(0,n) + S(1,n) + … + S(n-1,n) = 2n + 2(n-1) + … + 2

따라서 다음과 같이 표현할 수 있어요.

T(n) = 2n + 2(n-1) + … + 2

T(n) = 2  + … + 2(n-1) +2n

따라서 2T(n) = 2(n+1) + 2(n+1) + 2(n+1)

T(n) = (n+1) + (n+1) +… +(n+1)

n+1을 n번 더한 값이므로 T(n) = n(n+1) = n^2 + n 으로 표현할 수 있죠.

점근식 표기에서는 가장 높은 차수의 항만 사용하고 상수를 버리므로 O(n^2)라고 말할 수 있어요.

소스 코드

//순차 정렬(Sequential Sort)
#include <stdio.h>

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


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;
}

//정렬 과정을 출력하기 위한 함수입니다.
void ViewArr(int *arr, int n);
void SequenceSort(int *base, int n)
{
    int i, j;
    ViewArr(base, n);//현재 상태 출력
    for (i = 0; i<n; i++)
    {
        for (j = i; j<n; j++)
        {
            if (base[i]>base[j])//앞쪽 원소가 더 크면
            {
                SWAP(base[i], base[j]);//교환
                ViewArr(base, n);//상태 출력
            }
        }
    }
}

void ViewArr(int *arr, int n)
{
    int i = 0;
    for (i = 0; i<n; i++)
    {
        printf("%2d ", arr[i]);
    }
    printf("\n");
}

C언어 소스