TIL

190425_TIL(insertion sort)

컴퓨터공학기초

insertion sort(삽입 정렬)

insertion sort(삽입 정렬)이란?

  • 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
  • 최악의 경우의 삽입 정렬의 시간 복잡도는 O(n^2)로 버블정렬이나 선택 정렬과 같다. 하지만, 선택 정렬의 경우 빅오 표기법에 의해 숨겨진 상수항을 표현하면 정확히는 n^2 / 2 단계로 버블 정렬과 삽입 정렬보다 미세하게 빠르다고도 할 수 있다.
  • 하지만, 실질적으로 최악의경우는 드물게 일어난다. 가장 자주 일어나는 경우가 바로 평균의 경우이다. 선택 정렬의 경우 패스스루를 끝낼 매커니즘이 전혀 없기 때문에 최악부터 평균, 최선의 경우에 이르기까지 모두 n^2 / 2 단계가 걸린다. 이에 반해, 삽입 정렬은 패스스루를 빨리 끝낼 수 있는 메커니즘이 있기 때문에 최악의 경우에는n^2 단계, 평균의 경우에는 n^2 / 2, 최선의 경우에는 n단계가 걸린다.
  • 결론적으로. 어떤 데이터를 다루느냐에 따라 더 적절한 정렬 알고리즘을 적용하는 것이 옳다.


삽입정렬 매커니즘

  1. 인덱스 1의 값을 temp 라는 변수에 저장한다.
  2. 왼쪽에 정렬되어 있는 리스트의 값(현재는 인덱스 0의 값)과 temp의 값을 비교한다.
  3. 리스트의 값 > temp 이면 리스트의 값 오른쪽 원소에 리스트의 값을 저장하고 temp 값을 본래 리스트 값이 있던 인덱스(현재는 인덱스 0)의 삽입한다.
  4. temp > 리스트의 값이면 그대로 그 자리에 삽입한다.
  5. 인덱스의 값을 1씩 증가시키며 왼쪽의 정렬괸 리스트의 값과 temp 값을 비교하여 위 과정을 반복한다.




insertion sort(삽입 정렬) 코드 with python

  • 이해하기 위해 많은 주석을 달면서 진행하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def insertion_sort(array):
    for index in range(1, len(array)):
        position=index
        # 처음 0번 인덱스는 값이 하나이기 때문에 정렬된 리스트로 취급한다. 이 후 과정이 진행되면서 
        # 인덱스의 앞부분은 정렬된 리스트가 된다.
        # temp_value의 인덱스의 값을 임시 저장한다.
        # temp_value로 저장한 값이 배열 위로 솟구쳐 그 원래 공간이 공백이 된다고 생각하면 쉽다.
        temp_value=array[index]
        
        #  position > 0 --> positon의 왼쪽 즉,  position -1 과 비교를 하기 때문에 position 값이 배열의 0번 index 까지 갈 필요가 없다.
        #  array[position -1] > temp_value --> 배열의 1번 인덱스(패스스루마다 인덱스가 1씩 증가)의 값을 저장한 임시변수(temp_value) 와 왼쪽 값을 비교
        # temp_value 보다 왼쪽 값이 크면 왼쪽 값을 오른쪽(공백)으로 시프트 하고 다음 왼쪽 값과의 비교를 위하여 postion을 -1 감소 시킨다.
        # 이어서 새 position의 왼쪽 값이 temp_value보다 큰지 확인하고 temp_value보다 작은 값을 찾을 때까지 반복한다.
        while position > 0 and array[position -1] > temp_value:
            array[position]=array[position -1]
            position=position -1
        
        # 안쪽 while문이 끝나면 temp_value의 값을 공백에 삽입한다.
        array[position]=temp_value

테스트 코드

1
2
3
4
array=[4, 2, 7, 1, 3]
print(array)
insertion_sort(array)
print(array)




python tutor를 이용하여 삽입정렬 이해하기

  • pythontutor 의 기능을 이용하여 알고리즘의 실행순서를 파악해보았다.
  • 0번 인덱스와 1번 인덱스를 비교 후 첫번째 삽입으로 최초 정렬된 상태

  • temp_value > array[position -1]이기 때문에 while문을 돌지 않고 바로 빠져나와서 temp_value값을 그 자리 그대로 삽입한다.

  • 리스트에서 가장 작은 값인 1이 왼쪽의 정렬된 2, 4, 7 모두와 비교 후 0번 인덱스의 삽입

  • 모든 비교와 삽입이 끝난 후 정렬된 상태



참고서적

  • 누구나 자료구조와 알고리즘
Share