[카테고리:] <span>자료구조와 알고리즘 with C++</span>

2.1.3 순차 정렬 알고리즘 구현

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

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

반복(i:=0->n)

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

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

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

자료 형식에 관계없이 정렬할 수 있게 템플릿 함수로 작성합시다.

template <typename data, typename compare>
//순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
void sequential_sort(data *base, size_t n, compare com)
{
    //순차 정렬에서는 인덱스 0에서 n까지 최소값을 배치하는 것을 반복하죠.
    for(size_t i = 0; i<n; i++) //반복(i:=0->n)
    {
        //내부 반복문에서는 i 뒤에 원소들을 비교하면서 교환하는 것을 반복합니다.
        for(size_t j=i+1; j<n; j++)//반복(j:=i+1->n)
        {
            //만약 i번째 원소가 j번째 원소보다 더 크면 두 원소를 교환하죠.
            if(com(base[i],base[j])>0)//조건(compare(base[i], base[j]) > 0)
            {
                swap(base[i],base[j]); //교환(base[i],base[j])
            }
        }
    }
}

이제 테스트 코드를 작성합시다. 정렬할 원소 개수를 매크로 상수로 정의하세요.

#define MAX_DATA 1000

int main()
{
    Member *base[MAX_DATA];
    //먼저 정렬 알고리즘을 간단히 테스트 하기 위해 회원 개체를 10개만 생성하세요.
    MakeRandomMembers(base,10);
    //정렬 전의 회원 개체 배열을 출력하세요.
    cout<<"정렬 전"<<endl;
    ViewMembers(base,10);
    //번호 순으로 순차 정렬합시다. 그리고 정렬후에 회원 개체 배열을 출력하세요.
    sequential_sort(base,10,CompareByNum);
    cout<<"번호로 정렬 후"<<endl;
    ViewMembers(base,10);
    //이름 순으로 순차 정렬합시다. 그리고 정렬 후에 회원 개체 배열을 출력하세요.
    sequential_sort(base,10,CompareByName);
    cout<<"이름으로 정렬 후"<<endl;
    ViewMembers(base,10);
    //정렬에 사용한 회원 개체 배열을 해제화를 해야겠죠.
    RemoveMembers(base,10);

    //이번에는 알고리즘 성능을 테스트 해 보아요. 
    //알고리즘을 수행 전과 수행 후에 clock을 측정하여 차이를 계산하면 수행 속도를 평가할 수 있어요.
    clock_t st,et;

    //먼저 MAX_DATA 개수의 회원 개체를 생성하여 이름 순으로 정렬한 후에 속도를 출력하세요.
    MakeRandomMembers(base,MAX_DATA);
    cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;
    st = clock();    
    sequential_sort(base,MAX_DATA,CompareByName);    
    et=clock();
    cout<<"수행 속도:"<<et-st<<endl;
    RemoveMembers(base,MAX_DATA);

    //그리고 MAX_DATA/10 개수의 회원 개체를 생성하여 이름 순으로 정렬한 후에 속도를 출력하세요.
    MakeRandomMembers(base,MAX_DATA/10);
    cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;
    st = clock();
    MakeRandomMembers(base,MAX_DATA/10);
    sequential_sort(base,MAX_DATA/10,CompareByName);
    et=clock();
    cout<<"수행 속도:"<<et-st<<endl;
    RemoveMembers(base,MAX_DATA/10);
    return 0;
}

다음은 테스트에 사용한 전체 코드입니다.

//Program.cpp
#include "common.h"
template <typename data, typename compare>
//순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
void sequential_sort(data *base, size_t n, compare com)
{
    for(size_t i = 0; i<n; i++) //반복(i:=0->n)
    {
        for(size_t j=i+1; j<n; j++)//반복(j:=i+1->n)
        {
            if(com(base[i],base[j])>0)//조건(compare(base[i], base[j]) > 0)
            {
                swap(base[i],base[j]); //교환(base[i],base[j])
            }
        }
    }
}
#define MAX_DATA 1000
int main()
{
    Member *base[MAX_DATA];
    MakeRandomMembers(base,10);
    cout<<"정렬 전"<<endl;
    ViewMembers(base,10);
    sequential_sort(base,10,CompareByNum);
    cout<<"번호로 정렬 후"<<endl;
    ViewMembers(base,10);
    sequential_sort(base,10,CompareByName);
    cout<<"이름으로 정렬 후"<<endl;
    ViewMembers(base,10);
    RemoveMembers(base,10);

    clock_t st,et;

    MakeRandomMembers(base,MAX_DATA);
    cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;
    st = clock();    
    sequential_sort(base,MAX_DATA,CompareByName);    
    et=clock();
    cout<<"수행 속도:"<<et-st<<endl;
    RemoveMembers(base,MAX_DATA);

    MakeRandomMembers(base,MAX_DATA/10);
    cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;
    st = clock();
    MakeRandomMembers(base,MAX_DATA/10);
    sequential_sort(base,MAX_DATA/10,CompareByName);
    et=clock();
    cout<<"수행 속도:"<<et-st<<endl;
    RemoveMembers(base,MAX_DATA/10);
    return 0;
}

이를 수행하였을 때 나온 결과예요. 물론 수행하는 컴퓨터에 따라 결과는 조금씩 다를 수 있어요.

▷수행 결과

정렬 전

0000757147,이름0167851000

0301413356,이름0336971124

0659598368,이름0160567225

0391749387,이름0004890851

0035766290,이름0026239572

0473038164,이름0000597006

0003615544,이름0326051436

0392289610,이름0118341522

0170427798,이름0037215528

0675016433,이름0168544290

번호로 정렬 후

0000757147,이름0167851000

0003615544,이름0326051436

0035766290,이름0026239572

0170427798,이름0037215528

0301413356,이름0336971124

0391749387,이름0004890851

0392289610,이름0118341522

0473038164,이름0000597006

0659598368,이름0160567225

0675016433,이름0168544290

이름으로 정렬 후

0473038164,이름0000597006

0391749387,이름0004890851

0035766290,이름0026239572

0170427798,이름0037215528

0392289610,이름0118341522

0659598368,이름0160567225

0000757147,이름0167851000

0675016433,이름0168544290

0003615544,이름0326051436

0301413356,이름0336971124

수행 성능 테스트1 자료 개수:1000

수행 속도:4985

수행 성능 테스트2 자료 개수:100

수행 속도:50

수행 결과를 보면 번호 순과 이름 순으로 정렬하는 것을 알 수 있습니다.

그리고 수행 성능을 테스트 한 것을 보면 자료의 개수를 MAX_DATA로 할 때가 MAX_DATA/10으로 할 때보다 100배 가까이 느린 것을 알 수 있습니다.

순차 정렬 알고리즘을 분석하였을 때 계산한 O(n^2)와 결과가 비슷한 것을 알 수 있습니다.

알고리즘 성능을 분석할 때 수학적으로 계산해서 증명할 수 있으면 좋겠죠. 만약 그렇지 못한다면 지금처럼 실제 수행 시간을 측정하여 비교해 보세요.

자료구조와 알고리즘 with C++