삽입 정렬 !?
- 손 안의 카드를 정렬하는 방법과 같다.
- 새로운 카드를 기존의 정렬된 카드 사이에 올바른 위치게 끼워 넣는다.
- 2번째 원소부터 시작해서 그 앞(원소)와 비교하며 삽입할 위치를 찾고, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
- 최선의 경우, O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될만큼 좋은 정렬 알고리즘이다.
로직
- 정렬은 2번째 위치의 값을 standard에 저장한다.
- standdard와 이전에 있는 원소들과 비교하여 자리를 바꾸며 삽입해 나간다.
- 1번으로 돌아가서 다음 위치의 값을 standard로 지정하고 이 과정을 반복한다.
private static void insertionSort(int[] arr){
for(int i=1; i<arr.length; i++){
int standard = arr[i];
int index = i-1;
//넣을 위치를 찾았으니 그 뒤의 원소들을 한칸씩 뒤로 미는 과정
while((0<=index) && standard < arr[index]){
arr[index+1] = arr[index];
index--;
}
arr[index+1] = standard;
}
}- 첫 번째 원소 앞(왼쪽)에는 원소가 없기에 두번째 원소부터 탐색을 시작한다.
- standard에 임시로 기준 위치 값을 저장하고, index에는 기준 위치 이전의 위치를 저장한다.
- 이전 위치를 가리키는 index는 음수가 되지 않고, 이전 위치 값이 1번에서 선택한 기준 위치의 값보다 크다면 오른쪽으로 한 칸씩 이동 시켜준다. 그리고 index가 더 이전 위치를 가리키도록 한다.
- 2번에서 반복문이 끝나고 난 뒤, index에는 standard가 들어갈 위치의 인덱스-1의 위치를 가리키게 된다.
- 2번의 반복문에서 standard보다 큰 값들의 위치를 한 칸씩 오른쪽으로 밀었기에..!
- 그래서 (index+1) 위치에 standard가 들어갈 위치이기에 삽입해준다.
시간복잡도
- 최악의 경우(역으로 정렬되어 있을 경우), 선택 정렬과 마찬가지로 (n-1)+(n-2)+...+2+1 -> n(n-1)/2 즉, O(N^2)이다.
- 하지만, 모두 정렬 되어 있는 경우, 한 번씩만 비교하므로 O(N)의 시간 복잡도를 갖게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데 탐색을 제외한 오버헤드가 매우 적기 때문이다.
- 최선의 경우 : O(N)
- 평균과 최악의 경우 : O(N^2)
공간 복잡도
- 주어진 배열안에서 이루어지기에 O(N).
장점
- 알고리즘이 단순하다.
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
- 정렬하고자 하는 배열안에서 교환하는 방식이기에, 다른 메모리 공간이 필요하지 않다.
- 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다.
단점
- 비교적 많은 수들의 이동을 포함한다.
- 비교할 수가 많고 크기가 클 경우에 적합하지 않다. (배열의 길이가 길수록 비효율적)
- 평균화 최악의 시간 복잡도가 O(N^2)으로 비효율적이다.
developer