c언어 정렬 알고리즘에 대하여 알아보기(선택 정렬, 오름차순 정렬, 내림차순 정렬)

c언어 정렬 알고리즘에 대하여 알아보기(선택 정렬, 오름차순 정렬, 내림차순 정렬)

이번 시간에는 정렬을 하는 방법에 대하여 알아보도록 하겠습니다.

우리가 어떤 프로그램들을 보게 되면 오름차순 또는 내림차순으로 보기 좋게 배열이 되어있는 것을 볼 수가 있는데요,

그게 바로 정렬을 써서 나타낸 것입니다.

이렇게 정렬을 쓰면 뒤죽박죽하게 나열이 되어있던 숫자 또는 문자가 순서에 따라 나열이 되면서 가시성이 좋아집니다.

그럼 이를 어떻게 쓰면 좋은지 한 번 알아보도록 하겠습니다.

 

1. 선택 정렬

우리가 알아볼 정렬의 방법은 바로 선택 정렬입니다.

정렬을 하는 방법은 여러 가지가 있지만, 선택 정렬이 우리가 정렬에 대하여 이해하는데 제일 쉽고, 제일 접근하기도 쉬우며, 가장 많이 사용하는 정렬 방법들 중 하나입니다.

한 가지 예시로 1 부터 8까지 순서 없이 무작위로 나열이 되어있는 배열을 순서대로 다시 재배치를 시킨다고 가정을 해보겠습니다.

그럴 경우를 눈으로 보기 쉽게 표로 정리를 하자면 이러겠죠?

왼쪽 배열	오른쪽 배열	설명
{}	{5, 6, 3, 7, 8, 2, 1, 4}	초기상태
{1}	{5, 6, 3, 7, 8, 2, 4}	1선택
{1, 2}	{5, 6, 3, 7, 8, 4}	2선택
{1, 2, 3}	{5, 6, 7, 8, 4}	3선택
{1, 2, 3, 4}	{5, 6, 7, 8}	4선택
{1, 2, 3, 4, 5}	{6, 7, 8}	5선택
{1, 2, 3, 4, 5, 6}	{7, 8}	6선택
{1, 2, 3, 4, 5, 6, 7}	{8}	7선택
{1, 2, 3, 4, 5, 6, 7, 8}	{}	8선택

표로 정리를 하자면 다음과 같이 정리가 될 수 있습니다.

다시 말하면 배열이 두 개가 필요하고, 하나는 빈 배열, 하나는 숫자가 무작위로 배치가 된 배열이 필요하단 뜻입니다.

하지만 이럴 경우에는 필요 이상의 메모리를 사용을 할 수도 있기 때문에 메모리 낭비가 생길 수 있어서 입력 배열 외에 추가적인 메모리 공간을 사용하지 않고, 최소한의 메모리만 사용하는 선택 정렬 알고리즘을 예시로 들어서 설명을 드리고자 하는 것입니다.

해당 알고리즘에서는 배열을 하나만 쓰고 옮깁니다.

이제 여러분들은 이러한 의문을 가지게 될 것입니다.

분명히 배열이 두 개가 필요하다 그랬는데 하나만 쓰는 것이 가능하냐고 말이죠.

결론만 말씀드리자면 가능합니다.

제가 지금 말씀드리는 정렬 알고리즘의 이름이 선택 정렬 알고리즘이죠?
그리고 이 알고리즘을 이용하여 숫자를 순서대로 나열을 하겠다 그랬죠?
표에 보시면 제가 작은 값 부터 오름차순으로 정렬을 한 것이 보일 것입니다.

이렇다면, 제일 처음에 선택이 된 값이 최솟값일 거고,

그걸 앞으로 옮기는 일을 수행을 할 것입니다.

그래서 최솟값을 선택을 하여 앞으로 배치를 하고, 최솟값이 빠져나간 자리로 숫자를 밀어서 공간을 차지하도록 만들어주면서 재배치를 하는 것입니다.

그러한 원리로 재배치가 끝이 날 때까지 반복을 시킵니다.

그래서 제가 이번에 보여드릴 코드는 알고리즘입니다.

그러므로 프로그래밍을 할 시에 정렬을 해야 하는 상황이 온다면 이 알고리즘을 그대로 이용을 하시면 됩니다.

그럼 지금부터 코드를 작성을 해보도록 하겠습니다.

#include <stdio.h>

#define SIZE 8

int main()
{
    int A[SIZE] = {5, 6, 3, 7, 8, 2, 1, 4};

    int i, j, tmp, least;

    for(i = 0; i < SIZE - 1; i++)
    {
        least = i;

        for(int j = i + 1; j < SIZE; j++)
        {
            if(A[j] < A[least])
            {
                least = j;
            }
        }

        tmp = A[i];
        A[i] = A[least];
        A[least] = tmp;
    }

    for(i = 0; i < SIZE; i++)
    {
        printf("%d", A[i]);
    }

    printf("\n");

    return 0;
}

반응형

 

이렇게 작성을 할 수가 있습니다.

여기서 큰 for문 안에서 size - 1을 쓰는 이유는 숫자를 바꾸는 횟수는 (n - 1) 번이 됩니다.

그 이유는 최솟값을 앞으로 계속 배치를 하다 보면 최종적으로는 최댓값이 가장 뒤로 자동으로 가게 되어서 굳이 마지막 숫자는 배치를 할 필요가 없어지기 때문입니다.

그럼 결과를 보도록 하겠습니다.

1 2 3 4 5 6 7 8

결과가 잘 나온 것을 볼 수가 있습니다.

그리고 반대로 내림차순으로 정렬을 할 수도 있겠죠?

여기에서 조금만 바꿔주면 됩니다.

바로 보여드리도록 하겠습니다.

#include <stdio.h>

#define SIZE 8

int main()
{
    int A[SIZE] = {5, 6, 3, 7, 8, 2, 1, 4};

    int i, j, tmp, max;

    for(i = 0; i < SIZE - 1; i++)
    {
        max = i;

        for(int j = i + 1; j < SIZE; j++)
        {
            if(A[j] > A[max])
            {
                max = j;
            }
        }

        tmp = A[i];
        A[i] = A[max];
        A[max] = tmp;
    }

    for(i = 0; i < SIZE; i++)
    {
        printf("%d", A[i]);
    }

    printf("\n");

    return 0;
}

이렇게만 바꿔주면 됩니다.

여기서는 숫자가 큰 순서대로 배치가 되기 때문에 변수명을 least 대신 max로 바꿔주었습니다.

그리고 max 자리에 숫자가 배치가 되려면 배열 인덱스 max 보다 다른 배열에 있는 인덱스 넘버가 커야 하기 때문에 꺽쇠의 방향이 바뀌어 있는 것을 보실 수가 있습니다.

그럼 바로 결과도 보도록 하겠습니다.

8 7 6 5 4 3 2 1

결과도 잘 나오는 것을 보실 수가 있습니다.

그리고 여기서 주의사항이 있다면, 우리가 예전에 수 교환 프로그램을 작성을 했을 때처럼,

배열을 정렬시키기 위해서는 tmp라는 추가적인 변수가 필요합니다.

그렇지 않으면 기존에 있던 배열 원소가 교환 시에 저장을 할 공간이 없어서 파괴가 되니 주의를 하셔야 합니다.

 

여기까지 정렬을 하는 방법에 대하여 알아보았는데요,

다음 포스팅에서는 탐색을 하는 방법에 대하여 알아보도록 하겠습니다.

긴 글 읽어주신 독자분들께 진심으로 감사드립니다 ~