2.4.2 삽입 정렬 알고리즘 구현

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

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

    반복(i:=1->n)

        반복(j:=i->0)

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

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

            조건이 거짓일 때

                내부 반복문 탈출

참고로 2.1.2에서 공통으로 사용할 코드를 이용하세요.

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

 

 

다음은 실행 결과예요.

▷실행 결과

정렬 전

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

수행 속도:1560

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

수행 속도:31

 

삽입 정렬도 결과를 보면 자료 개수가 MAX_DATA일 때 MAX_DATA/10일 때보다 100배 정도 느린 것을 알 수 있습니다. 앞에서 알고리즘 성능을 분석할 때 O(n^2)와 비슷하죠. 그렇지만 내부 반복문을 탈출하는 조건이 있어서 앞의 세(순차, 거품, 선택) 가지 정렬 알고리즘보다 빠른 것을 알 수 있어요.


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