[정렬] Insertion Sort - JS, Python

삽입정렬 알고리즘

삽입 정렬은 왼쪽에서 오른쪽으로 가면서 요소들을 왼쪽 요소들과 비교하여 알맞은 자리에 삽입하는 형식의 정렬 방법

주의  첫번째 값은 고정되어있음

출처 : 위키피디아

1. 첫번째 값을 고정시킨 채 오른쪽 값과 첫번째 값을 비교한다

2. 왼쪽 값이 오른쪽 값보다 크면 오른쪽 값을 왼쪽으로 삽입한다 (반복)

3. 만약 왼쪽값이 오른쪽 값보다 작은 경우 삽입을 멈춘 뒤 값을 고정시킨다

삽입정렬은 항상 왼쪽 비교 대상 데이터들이 정렬되어 있다는 가정하에 진행된다

Big O

• 삽입 정렬 시간 복잡도는 O(N^2)이며, 선택정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됨
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태면 매우 빠르게 동작

WORST O(N^2) - 값을 전부 비교하며 교환해야 하는 경우

 

BEST O(N) - 값이 정렬되어 있는 경우 

 

장점

삽입 정렬도 in place 알고리즘이기 때문에 메모리가 절약된다

선택정렬보다 구현하긴 살짝 까다롭다 하지만 선택 정렬과 다르게 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트 하는 용도로 사용될 수 있음

* in place란?

자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻

단점

자료의 개수가 많아질수록 성능이 매우 떨어짐 (최악의 경우 O(n^2))

 

Python 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)): # 맨앞 고정
    for j in range(i, 0, -1): # idx i부터 1까지 1씩 감소하면서 반복
        if array[j] < array[j-1]: # j위치에 있는 값이 바로 앞의 값보다 작으면
            array[j], array[j-1] = array[j-1], array[j] # swap
        else: # 자기보다 작은 데이터를 만나면 고정  
            break

print(array)

 

JS 코드

let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for (let i = 1; i < array.length; i ++) {
    for (let j = i; j > 0; j-- ) {
        if (array[j] < array[j-1]) {
            swap = array[j]
            array[j] = array[j-1]
            array[j-1] = swap
        }
        else {
            break
        }
    }
    console.log(`${i}번째 회전: ${array}`)
}