자료구조와 알고리즘 with C++ - 언제나 휴일

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

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

반복(i:=n->1)

반복(j:=1->i)

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

교환(base[j-1],base[j])

template <typename data, typename compare>
//거품 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
void bubble_sort(data *base, size_t n, compare com)
{
    for(size_t i=n; i>1; i--) //반복(i:=n->1)
    {
        for(size_t j=1; j<i; j++) //반복(j:=1->i)
        {
            if(com(base[j-1],base[j])>0)//조건(compare(base[j-1], base[j]) > 0)
            {
                swap(base[j-1], base[j]);//교환(base[j-1],base[j])
            }
        }
    }
}

테스트 코드도 2.1.3에서 작성한 코드에서 sequential_sort 부분을 bubble_sort로 변경하세요.

#define MAX_DATA 1000

int main()
{
    Member *base[MAX_DATA];
    //버블 정렬이 잘 동작하는지 10개 원소를 번호 순으로 정렬하여 확인하고 이름 순으로 정렬하여 확인하세요.
    MakeRandomMembers(base,10);
    cout<<"정렬 전"<<endl;
    ViewMembers(base,10);
    bubble_sort(base,10,CompareByNum);
    cout<<"번호로 정렬 후"<<endl;
    ViewMembers(base,10);
    bubble_sort(base,10,CompareByName);
    cout<<"이름으로 정렬 후"<<endl;
    ViewMembers(base,10);
    RemoveMembers(base,10);

    //그리고 MAX_DATA 개일 때 수행 속도와 MAX_DATA/10 개일 때 수행 속도를 비교해 보세요.
    clock_t st,et;

    MakeRandomMembers(base,MAX_DATA);
    cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;
    st = clock();    
    bubble_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);
    bubble_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

수행 속도:4357

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

수행 속도:36

거품 정렬도 결과를 보면 자료 개수가 MAX_DATA일 때 MAX_DATA/10일 때보다 100배 정도 느린 것을 알 수 있습니다. 앞에서 알고리즘 성능을 분석할 때 O(n^2)와 비슷하죠.

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

2.2.2 거품 정렬 알고리즘 구현