삽입 정렬
Insertion Sort
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
여러분은 카드 게임을 하고 있다. 카드를 나눠 받은 뒤, 내 손 안에 무작위 순서로 들어온 카드를 정리한다고 생각해보자. 카드를 정리하는 많은 방법 중에 두 번째 카드부터 앞의 카드들과 비교하여 넣을 위치를 정한 다음, 그 사이에 카드를 넣어 정리하는 방법을 사용해 카드를 정리했다면 삽입 정렬을 사용해봤다고 이야기할 수 있다.
Process
1.
정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2.
temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다.
3.
'1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.
python
def insertion_sort(x):
for size in range(1, len(x)):
val = x[size]
i = size
while i > 0 and x[i - 1] > val:
x[i] = x[i - 1]
i -= 1
x[i] = val
Python
복사
JavaScript
const insertionSort = function (arr, func) {
for (let i = 1; i < arr.length; i++) {
let value = arr[i];
let target = i;
while (i > 0 && arr[target - 1] > value) {
arr[target] = arr[target - 1];
target--;
}
arr[target] = value;
}
};
JavaScript
복사
•
시간복잡도 : best - O() , average, worst - O()
모두 정렬되어 있는 경우 한 번씩만 비교하면 됨 → Best O()
역으로 정렬되어 있는 경우 → Worst O()
•
공간복잡도 : O()
주어진 배열 안에서 교환을 통해 정렬이 이루어지므로 O()
장점
•
알고리즘이 단순
•
대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적
•
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 ⇒ 제자리 정렬 (In-place sorting)
•
안정 정렬 (Stable Sort)
•
Selection Sort나 Bubble Sort보다 상대적으로 빠름
단점
•
평균과 최악의 시간복잡도가 O()으로 비효율적
•
배열의 길이가 길어질수록 비효율적