2.1.3 순차 정렬 알고리즘 구현

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

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

    반복(i:=0->n)

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

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

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

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

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

 

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

 

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

▷수행 결과

정렬 전

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)와 결과가 비슷한 것을 알 수 있습니다.

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


실습한 파일은 언제나 휴일 프로그램 소스 사이트에 있습니다.