[알고리즘 개념] 삽입정렬 (Insertion Sort)

기본 정렬 알고리즘

삽입 정렬 (Insertion Sort)
리스트의 값을 하나씩 살펴보며 적절한 위치에 삽입한다

• 정렬 순서

  1. 첫 번째 숫자를 삽입한 것이라 하고 두 번째 숫자부터 확인한다

  2. 현재 선택한 숫자 바로 앞부터 처음까지 왼쪽으로 이동하면서 가리킨 숫자가 선택한 숫자보다 클 시 가리킨 숫자를 뒤로 옮긴다

  3. 현재 선택한 숫자보다 가리킨 숫자보다 작을 시 멈추고 해당 자리에 삽입한다

• 예시

  순서	리스트	진행 상황
  0	[ 3, 6, 5, 7, 2 ]	초기값
  1	[ 3, [6], 5, 7, 2 ]	3 삽입, 6 확인
  2	[ 3, 6, [5], 7, 2 ]	6 삽입, 5 확인
  3	[ 3, 5, 6, [7], 2 ]	5 삽입, 7 확인
  4	[ 3, 5, 6, 7, [2]]	7 삽입, 2 확인
  5	[ 2, 3, 5, 6, 7 ]	2 삽입, 끝

• 코드

def insert_sort(x):
    for i in range(1, len(x)):
	j = i - 1
	key = x[i]
	
	while x[j] > key and j >= 0:
	    x[j+1] = x[j]
	    j = j - 1
		
	x[j+1] = key
	
    return x
        

• 시간 복잡도 비교

  기본 정렬 알고리즘	최적	평균	최악
  선택 정렬	N^2	N^2	N^2
  버블 정렬	N^2	N^2	N^2
  삽입 정렬	N	N^2	N^2