[Algorithm] 삽입 정렬 - Insertion Sort (Python)

📌 삽입 정렬

버블 정렬의 비효율성을 개선하기 위해 등장한 삽입 정렬은 정렬되지 않은 값을 정렬된 값들과 비교하여, 알맞은 자리에 삽입해주는 정렬이다.

Stable 정렬이면서 In-place 정렬이며, 버블 정렬의 비교 및 교환 횟수를 줄임으로써 높은 효율을 보여준다.

아이디어

1. i번째 원소와 0부터 i-1번째 원소를 비교한다.
2. 이 때, i번째 값보다 작은 값을 발견하면 그 위치에 i번째 원소를 삽입한다.
3. 위 과정을 반복한다.

복잡도 분석

• 별도의 추가 공간을 사용하지 않고, 기존의 리스트 내에서만 원소의 위치 변화가 일어나기 때문에 O(1)의 공간 복잡도를 갖는다.
  
  
• 입력 자료가 정렬되어 있는 경우에는 N-1번의 루프가 실행되고, 1번의 비교와 삽입이 이루어지기 때문에 O(N)이다.
  하지만, 입력 자료가 역순으로 정렬되어 있는 최악의 경우 N-1번의 루프가 실행되는 동안 N-1번의 비교가 발생한다. 이를 수식으로 나타내면 다음과 같다.
  
  (N-1) + (N-2) + ... + 2 + 1 = N * (N-1) / 2
  
  따라서 삽입 정렬의 평균 시간 복잡도는 O(N^2)이다.
  
  

특징

👍 장점

• 입력 데이터가 정렬되어 있을 경우 속도가 빠르다.
• 이미 정렬된 값은 교환이 일어나지 않는다.

👎 단점

• 입력 데이터가 역순으로 정렬되어 있을 수록 성능이 현저히 떨어진다.
• 삽입을 구현해야 하므로 자료구조에 영향을 많이 받는다.
• 루프가 거듭될수록 정렬 범위가 넓어진다.

구현

for i in range(1, n):
	key = arr[i]
	idx = i

	while idx > 0 and arr[idx-1] > key:
		arr[idx] = arr[idx-1]
		idx -= 1

	arr[idx] = key

--

참고 사이트
🙇🏻‍♂️ https://www.daleseo.com/sort-insertion/
🙇🏻‍♂️ https://jbhs7014.tistory.com/180