Insertion Sort

참고 문헌

<C언어로 쉽게 풀어쓴 자료구조 내용 >

< 윤성우의 열혈 자료구조 내용 >

< 쉽게 배우는 알고리즘 내용  >

 

삽입 정렬의 장점과 단점

삽입정렬은 연결리스트에서 최적. 그리고 정렬할 데이터들이 얼추 정리가 됬을때, 가장 최적화.
최악은 자료들이 정 반대로 정렬되어있을때 연산량이 많다.

 

구현 version1

삽입 정렬의 원리는 손 안의 카드를 정렬하는 방법과 유사하다.

새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써, 정렬이 유지되게 한다.

이와 같은 작업을 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.

 

[그림 1]

정렬되어 있지 않은 리스트의 첫 번째 숫자가 정렬된 리스트의 어느 위치에 삽입되어야 하는가를

판단한 후, 해당 위치에 이 숫자를 삽입하게 되면 정렬된 리스트의 크기는 하나 커지게 되고,

정렬이 되지 않은 리스트의 크기는 하나 줄어들게 된다.

이러한 삽입 연산을 정렬되지 않은 리스트가 없어질 때까지 반복하게 되면 전체 리스트가 정렬된다.

전체 리스트 { 5, 3, 8, 1, 2, 7 }를 삽입 정렬하는 과정이 아래의 [그림 2]이다.

 

[그림2 ]

아래는 삽입정렬 알고리즘 의사 코드 

알고리즘 설명

1. 인덱스 1부터 시작한다. 인덱스 0은 이미 정렬된 것으로 볼 수 있다.

2. 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

3. 현재 정렬된 배열은 i - 1까지 이므로, i - 1번째부터 역순으로 조사한다.

4. j값이 음수가 아니어야 하고, key값보다 정렬된 배열에 있는 값이 크면

5. j번째를 j+1 번째로 이동한다.

6. j를 하나 감소한다.

7. j번째 정수가 key보다 작으므로, j+1 번째가 key값이 들어갈 위치이다. 

 

아래의 [ 그림 3 ]에서 i = 3 인 경우에 정렬된 왼쪽 리스트에 어떻게 삽입이 되는지를

보여준다.

 

[그림 3 : 삽입 정렬의 하나의 삽입 과정 ]

 

프로그램 실행결과

소스 파일

main.c

0.00MB

 

구현 version2

삽입정렬은 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여

정렬된 i+1개 짜리 배열을 만드는 과정을 반복한다.

선택정렬과 버블정렬이 n개짜리 배열로부터 시작하여 그 크기를 하나씩 줄여나가는데 반하여,

삽입정렬은 1개짜리 배열로부터 시작하여 그 크기를 하나씩 늘려나가는 정렬이다.

 

삽입정렬 알고리즘 의사코드

알파의 for루프는 문제의 크기를 하나씩 키워나가는 역할을 한다.

위의 알고리즘에서 A[i]에 관심을 두는 시점, 즉, 베타를 수행하기 직전 시점에

A[1...(i-1)]은 항상 정렬이 되어 있다.

베타를 수행하고 나면 A[i]까지 정렬이 된다.

위의 알고리즘을 좀 더 자세히 기술하면 아래와 같다.

 

위의 알고리즘의 for루프는 n-1번 순환한다.

while루프는 최대 n-1번 순환한다.

 

프로그램 실행결과

소스 파일

main.c

0.00MB