🌱 Insertion Sort ( 삽입 정렬 )
👉🏻 삽입 정렬 (揷入整列, insertion sort)은 리스트의 앞에서부터 차례대로 이미 정렬된 리스트와 비교하며, 위치를 찾아 요소를 삽입하여 정렬하는 알고리즘입니다. 매 순서마다 해당 요소의 위치를 찾기 위해 리스트의 모든 요소와 비교합니다. 가장 흔한 예로 손에 들고 있는 카드를 정렬하는 방법으로 소개됩니다.
-
요소의 올바른 위치를 비교하면서 찾는 비교 정렬 알고리즘 입니다.
-
정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는 제자리 정렬 알고리즘 이며, 내부 알고리즘입니다.
🪴 장 점
- 구현이 간단한 알고리즘 중 하나로, 기본적으로 작은 데이터 세트에서 다른 복잡한 정렬보다 효율적입니다.
- 이미 부분적으로 정렬된 데이터 세트에서 매우 효율적입니다. 최선의 경우 O(n)의 시간복잡도를 가집니다.
- 안정적 정렬 방법으로 요소의 상대적 순서가 보장됩니다.
- 추가적인 메모리 소비가 작습니다.
🪴 단 점
- 요소의 이동이 많아 데이터 세트의 크기가 크면 적합핮 ㅣ않습니다.
- 역순으로 정렬된 경우와 같은 최악의 경우에는 O(n²)의 시간복잡도를 가집니다.
- 데이터 상태에 따라 성능 편차가 매우 큽니다.
☀️ Operations of Insertion Sort ( 작동 )
-
두번째 위치한 요소부터 시작해 이전의 요소와 비교하여 삽입할 위치를 찾고, 해당 위치에 요소를 삽입하기 위해 나머지 요소들을 한 칸씩 뒤로 이동시켜 공간을 만들어 삽입하는 정렬 알고리즘입니다.
-
사실상 정렬된 부분과 정렬되지 않은 부분으로 분할되며, 정렬되지 않은 부분의 값을 선택하여 정렬된 부분에서 올바른 위치를 찾아 삽입합니다.
☀️ Time and Space Complexity Analysis ( 시·공간 복잡도 )
-
입력자료가 역순인 최악의 경우 O(n²)의 시간복잡도를 가집니다. 외부 루프 안의 각 내부 루프마다 i번의 비교를 수행하고, 각 외부 루프 단계마다 (i + 2)번의 이동을 합니다. 또한 해당 요소는 이전 요소보다 항상 작으므로 결국 n번째 숫자에 대해 n-1번의 비교를 해야해 O(n²)의 시간복잡도를 가집니다.
-
이미 정렬이 되어 있는 최선의 경우, 해당 요소가 이전 요소보다 크기 전까지 반복하므로 이미 정렬이 되어있으면 항상 해당 요소가 이전 요소보다 크므로 n번만 비교해 O(n)의 시간복잡도를 가집니다. 이동없이 1번의 비교만 이루어지면 O(1)의 시간복잡도를 가질 수 있습니다.
-
평균적으로 O(n²)의 시간복잡도를 가집니다.
-
최선의 경우 O(1)의 공간복잡도를 가지고, 평균적으로 O(n) 공간복잡도를 가집니다.
☀️ Implementation of Insertion Sort ( 구현 )
🕶️ Basic Implementation (기본 구현)
function insertionSort(arr) {
let j, target;
for(let i = 1; i < arr.length; i++) {
j = i - 1;
target = arr[i];
while(arr[j] > target && j >= 0) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = target;
}
return arr
} 🕶️ Recursive Implemente (재귀적 구현)
function recursiveInsertionSort(arr, len) {
// base case
if(n <= 1) return;
// recursive
recursiveInsertSort(arr, len - 1);
const last = arr[n - 1];
let j = n - 2;
while(j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}👀 Reference
