Backend/알고리즘
삽입 정렬( Insertion sort ) 알고리즘
chjysm
2022. 12. 12. 20:02
삽입 정렬 알고리즘?
배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,
자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘.
삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
특징
장점
- 레코드 수가 적거나 대부분의 레코드가 이미 정렬되어 있다면 매우 효율적이다.
단점
- 레코드 이동이 많을 수 있다.
- 레코드 수가 많고 크다면 적합하지 않다.
구현
public static void insertionSort( int[] target ) {
for( int i = 1; i < target.length; i++ ){
int pick = target[i];
int j;
for( j = i-1; j >= 0 && target[j] > pick; j-- ){
// 오른쪽이동
target[j+1] = target[j];
}
target[j+1] = pick;
}
}
시간 복잡도
최상 : O(n)
평균, 최악 : O(n^2)
참고
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io