삽입정렬
주어진 배열 a[]를 그대로 사용
전체 배열중에서 정렬되지 않은 부분의 첫번째 원소를 "꺼내서" 정렬된 부분의 알맞은 위치에 삽입
이때, 전체배열은, 정렬 된 부분 / 삽입할 원소(꺼낸 원소) / 정렬 안 된 부분 으로 나뉜다.
레코드를 계속 이동시켜야 하므로 레코드의 크기가 큰 경우에 불리
almost sorted file인 경우에 유리
실행시간은 입력자료의 순서에 민감
안정적인 알고리즘
제자리 정렬
- 비교시 배열의 범위를 벗어나는것을 방지하기 위해 감시 키 필요
a[0]자리에 가장 작은값보다 더 작은 값을 넣어서 경계키로 사용
초기에 a[1]은 삽입되어있는 상태,
a[2]를 꺼내서 a[1]의 값과 비교, 알맞은 순서로 삽입
(이 과정에서 a[2]가 a[1]의 값 보다 작다면 a[1]을 꺼내서 a[2]의 자리에 넣고,
a[2]에서 꺼낸 원소를 a[1]의 자리에 넣는다.)
두번째 단계에서는 a[3]의 원소를 꺼내 a[1], a[2]의 배열 중 들어갈 자리가 있는 지 확인,
없으면 다시 a[3]의 자리에 넣고 있다면, a[1]~a[2]의 원소들을 한칸씩 옮겨가며 자리를 확보->삽입
..
..
..
마지막에 a[n]의 원소를 a[1]~a[n-1]까지의 배열 사이에 순서에 알맞게 들어갈 자리가 있는지 확인,
있다면 원소를 한칸씩 옮기며(이때 교환이 아니라 이동이라는걸 명심, 앞 부분은 이미 정렬된 순서)
알맞은 위치의 공간을 확보한 후 삽입.
만약 a[n-5]자리에 a[n]에서 꺼낸 원소가 들어가야 한다면,
a[n-1]의 원소를 a[n]자리로
a[n-2]의 원소를 a[n-1]의 자리로
a[n-3]의 원소를 a[n-2]의 자리로
a[n-4]의 원소를 a[n-3]의 자리로
a[n-5]의 원소를 a[n-4]의 자리로 옮긴 후
a[n-5]의 자리에 a[n]에서 꺼낸 원소를 삽입
..
시간복잡도는 O(N^2)
InsertionSort(a[], n) { // 원소 v는 a[i], 1 <= i <= n, // 원소 v(=a[i], 1 <= i, 1 <= i <= n)를 부분배열 a[1 : i-1]에 오름차순 순으로 삽입 for ( i <- 2; i <= n; i <- i+1 ) do { // 두 번째 원소 a[2]부터 v <- a[i]; // v는 임시 저장공간 j <- 1; - while ( a[j-1] > v ) do { a[j] <- a[j-1]; // a[j-1]; } / while 문 A[j] <- v; // v를 빈자리에 삽입 } // for end InsertionSort() }
|
'General > Algorithm' 카테고리의 다른 글
[알고리즘] 정렬 알고리즘 - 퀵 정렬(QuickSort) 기본 알고리즘 (2) | 2009.11.30 |
---|---|
[알고리즘] 기초 정렬 알고리즘 - 쉘 정렬(ShellSort) (0) | 2009.11.30 |
[알고리즘] 기초 정렬 알고리즘 - 버블 정렬(Bubble Sort) (0) | 2009.11.30 |
[알고리즘] 기초 정렬 알고리즘 - 선택 정렬(Selection Sort) (0) | 2009.11.30 |
[알고리즘] 정렬(sorting)의 개요- 레코드(record), 키(key) (0) | 2009.11.30 |