삽입 정렬 "특정한 테이터를 적절한 위치에 '삽입'한다"

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린편이다.

 

'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?'

 

삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다.

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미이다.

 

삽입 정렬 특징

1) 데이터가 거의 정렬 되어 있을 때 효율적이다.

2) 삽입 정렬은 특정 데이터가 적절한 위치에 들어가기 전, 그 앞까지의 데이터는

이미 정렬되어 있다고 가정한다.

3) 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징

 

예시 

step0) 첫 번째 데이터 '7'은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재, 우리는 카드를 오름차순으로 정렬하고자 '7'의 왼쪽에 삽입한다.

7 5 9 0 3 1 6 2 4 8

 

step1) 이어서 '9'가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지이며 현재 '9'는 '5'와 '7'보다 크기 때문에 원래 자리 그대로 둔다.

5 7 9 0 3 1 6 2 4 8

 

step2) 이어서 '0'이 어떤 위치에 들어갈지 판단한다. '0'은 '5', '7', '9'과 비교했을 땨 가장 작기 때문에 첫번째 위취에 삽입한다.

5 7 9 0 3 1 6 2 4 8

 

반복

 

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): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[ j] < array[ j - 1]: # 한 칸씩 왼쪽으로 이동
            array[ j], array[ j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

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

 

이 예제에서 헷갈린 부분

i 와 j 의 부분이 헷갈렸다. i 는 계속해서 늘어나고 j 는 주어진 i 부터 -1 씩 줄어든다.

줄어든 j 값을 기준으로 한 칸씩 이동 시킨 후(계속해서 더 큰값을 만나면 이동 시킨다.)

지금 값 j 보다 작은 데이터를 만나면 그 위치에서 멈춘다.

 

선택정렬과 차이가 있음을 인지해야한다. 

선택정렬은 특정 값을 만나면 그값과 바꾸는 것이다.

 

 

<출처> 이 것이 코딩 테스트다 (나동빈 지음)