All Articles

알고리즘 - 삽입 정렬(Insertion sort)

삽입 정렬(Insertion sort)이란

1번 인덱스(두 번째 인덱스)부터 시작해 앞에 있는 모든 값과 비교한다. 기준 값보다 큰 값을 만나면 위치를 바꿔준다. 앞에 요소가 남아있지 않을 때까지 반복한다.

삽입 정렬 예시

요소가 4개일 때

nums = [2, 4, 1, 3]

  1. 1번 인덱스를 기준으로 0번 인덱스와 값 비교
  2. 2, 4 비교
  3. 4는 2보다 크므로 자리 바꿈 없음 - [2, 4, 1, 3] - 1턴 완료
  4. 2번 인덱스를 기준으로 1~0번 인덱스와 값 비교
  5. 1, 4 비교
  6. 1은 4보다 작으므로 자리 바꿈 - [2, 1, 4, 3]
  7. 1, 2 비교
  8. 1은 2보다 작으므로 자리 바꿈 - [1, 2, 4, 3] - 2턴 완료
  9. 3번 인덱스를 기준으로 2~0번 인덱스와 값 비교
  10. 3, 4 비교
  11. 3은 4보다 작으므로 자리 바꿈 - [1, 2, 3, 4]
  12. 3, 2 비교
  13. 3은 2보다 크므로 자리 바꿈 없음 - [1, 2, 3, 4]
  14. 3, 1 비교
  15. 3은 1보다 크므로 자리 바꿈 없음 - [1, 2, 3, 4] - 3턴 완료

요소가 5개일 때

nums = [7, 3, 2, 4, 1]

  1. 1번 인덱스를 기준으로 0번 인덱스와 값 비교
  2. 3, 7 비교
  3. 3은 7보다 작으므로 자리 바꿈 - [3, 7, 2, 4, 1] - 1턴 완료
  4. 2번 인덱스를 기준으로 1~0번 인덱스와 값 비교
  5. 2, 7 비교
  6. 2는 7보다 작으므로 자리 바꿈 - [3, 2, 7, 4, 1]
  7. 2, 3 비교
  8. 2는 3보다 작으므로 자리 바꿈 - [2, 3, 7, 4, 1] - 2턴 완료
  9. 3번 인덱스를 기준으로 2~0번 인덱스와 값 비교
  10. 4, 7 비교
  11. 4는 7보다 작으므로 자리 바꿈 - [2, 3, 4, 7, 1]
  12. 4, 3 비교
  13. 4는 3보다 크므로 자리 바꿈 없음 - [2, 3, 4, 7, 1]
  14. 4, 2 비교
  15. 4는 2보다 크므로 자리 바꿈 없음 - [2, 3, 4, 7, 1] - 3턴 완료
  16. 4번 인덱스를 기준으로 3~0번 인덱스와 값 비교
  17. 1, 7 비교
  18. 1은 7보다 작으므로 자리 바꿈 - [2, 3, 4, 1, 7]
  19. 1, 4 비교
  20. 1은 4보다 작으므로 자리 바꿈 - [2, 3, 1, 4, 7]
  21. 1, 3 비교
  22. 1은 3보다 작으므로 자리 바꿈 - [2, 1, 3, 4, 7]
  23. 1, 2 비교
  24. 1은 2보다 작으므로 자리 바꿈 - [1, 2, 3, 4, 7] - 4턴 완료

귀납적 판단

  • 기준 인덱스 범위는 1부터 데이터 전체 길이에 1을 뺀 값까지다.
  • 기준 인덱스와 비교할 나머지 인덱스 범위는 기준 인덱스에 1 뺀 값부터 -1씩 감소해서 0까지다.
  • 전체 로직 반복 횟수는 데이터 전체 길이에서 1을 뺀 값만큼이다.
  • 만약 기준 값과, 바로 앞에 위치한 값을 비교했을 때 기준 값이 크다면 그 턴은 종료해도 된다. 앞에는 이미 정렬된 값이므로 반복문을 더 돌리면서 비교할 이유가 없다.

버블 정렬 알고리즘 시나리오

  1. 기준 인덱스 범위를 지정해 인덱스 값이 커지도록 반복문을 돌린다.
  2. 기준 값과 비교할 값의 인덱스 범위를 지정해 반복문을 돌린다.
  3. 이때 기준 값이 비교할 값보다 작다면 위치를 바꿔준다.
  4. 앞에 값이 없을 때까지 반복하되, 기준 값이 비교할 값보다 크면 break로 반복문을 빠져나온다.

코드 작성

def insertionsort(nums):
  for standard in range(1, len(nums)):
    for idx in range(standard-1, -1, -1):
      if nums[standard] < nums[idx]:
        nums[standard], nums[idx] = nums[idx], nums[standard]
        standard = idx
      else:
        break
  return nums

검증

import random

# 0부터 99까지 숫자 중 50개를 무작위로 뽑아서 리스트 생성
nums = random.sample(range(100), 50)
print(insertionsort(nums))

복잡도

이중 for문이므로 O(n2)

기억해두기

기준 값을 이동시킨 후 계속 기준 값으로 유지시키기

if nums[standard] < nums[idx]:
  nums[standard], nums[idx] = nums[idx], nums[standard]
  standard = idx

Published 21 Aug 2020