2.2.2 순차 정렬 알고리즘 구현

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

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

    반복(i:=0->n)

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

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

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

 

이번에는 순차 정렬 알고리즘을 구현하는 예를 보여드릴게요.

 

 먼저 공통으로 사용할 파일을 프로젝트 폴더에 복사한 이후에 프로젝트에 추가하세요. 그리고 헤더 파일을 포함합니다. 이후의 작업에서는 언제나 필요하며 별다른 언급을 하지 않겠습니다.

여기에서 정의할 버블 정렬은 원소 형식에 관계없이 동적으로 생성한 개체의 집합을 정렬하게 정의할 것입니다. 이를 위해 void * 형식을 Element 형식 이름으로 정의할게요.

매크로 함수로 Element 형식을 교환하는 swap 메서드를 정의합시다.

순차 정렬은 n개의 원소가 있는 배열의 주소와 원소 개수 및 비교 알고리즘을 입력 인자로 필요합니다.

외부 반복문에서는 루프 인덱스 변수 i를 0에서 순차적으로 증가시키며 내부 반복문을 수행합니다.

내부 반복문에서는 i의 다음 위치부터 순차적으로 다음 요소들의 인데스로 증가하며 비교 작업을 반복합니다.

만약 인덱스 i의 요소가 인덱스 j의 요소보다 크면 둘의 위치를 교환합니다.

위 알고리즘이 제대로 작성한 것인지와 수행 속도를 확인해 봅시다.

 

먼저 시뮬레이션에서 사용할 배열을 선언합니다.

시뮬레이션을 하기 위해 필요한 초기 작업을 수행하는 함수를 작성합시다.

시뮬레이션을 초기화하는 함수에서는 도서 개체를 생성하는 작업을 할 것입니다. 도서 제목과 저자명을 입력받기 위한 변수와 여러 개의 도서 개체를 만들기 위해 Loop 수행 횟수를 기억할 변수를 선언합니다.

도서 제목과 번호로 비교하는 함수를 정의합시다.

배열에 보관한 도서 개체 정보를 출력하는 함수를 정의합시다.

먼저 제대로 동작하는지 확인하는 시뮬레이션 함수를 작성합시다.

수행 속도를 확인하기 위한 시뮬레이션 함수도 작성합시다.  속도를 확인하기 위해 clock_t 변수를 두 개 선언합니다. 하나는 정렬을 수행하기 전의 시간을 기억하기 위한 변수이고 하나는 수행한 후의 시간을 기억하기 위한 변수입니다. 참고로 clock_t 형식은 시스템에서 자원 사용에 관한 회계를 위해 정의한 논리적 시간으로 운영체제에 따라 단위가 다릅니다. 여기에서는 상대적인 시간을 비교하기 위함이므로 단위가 얼마인지는 중요하지 않습니다.

시뮬레이션을 마치고 동적으로 생성한 도서 개체를 소멸하는 해제화 함수도 작성합시다.

이제 진입점인 main 함수를 구현합시다.

정상적으로 동작하는지와 정렬할 원소 개수와 수행 속도의 관계가 어떤지 확인해 보세요.

 

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

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

▷수행 결과

정렬 전

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

 

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