[Algorithm] 정렬 알고리즘_4(단순 삽입 정렬)

06-4 단순 삽입 정렬

단순 삽입 정렬 알아보기

단순 삽입 정렬(straight insertion sort): 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점이 다릅니다.

정렬된 부분과 아직 정렬되지 않은 부분에서 다시 배열을 구성할 경우에는 다음 작업을 n - 1번 반복하면 정렬이 완료됩니다.

• 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입합니다.

단순 삽입 정렬

단순 삽입 정렬의 알고리즘 개요는 다음과 같습니다.

for i in range(1, n):
	tmp ← a[i]를 넣습니다.
    tmp를 a[0], ···, a[i -1]의 알맞은 위치에 삽입합니다.

단순 삽입 정렬에서 원소 삽입

위 그림에서 반복 제어 변수 j에 i를, tmp에 a[i]를 대입하고 다음 조건 중 하나를 만족할 때까지 j를 1씩 감소시키면서 대입 작업을 반복합니다.

• 종료 조건 1: 정렬된 배열의 왼쪽 끝에 도달한 경우
• 종료 조건 2: tmp보다 작거나 키값이 같은 원소 a[j - 1]을 발견한 경우

이때 드모르간 법칙을 적용하면 다음 2가지 조건이 모두 성립할 때까지 스캔 작업을 반복합니다.

• 계속 조건 1: j가 0보다 큰 경우
• 계속 조건 2: a[j - 1]의 값이 tmp보다 큰 경우

이 과정을 마치면 원소 a[j]에 삽입할 값인 tmp를 대입합니다.

- 드모르간 법칙 참고

2022.11.25 - [Code/Algorithm] - [Algorithm] 기본 자료구조와 배열_2

[Algorithm] 기본 자료구조와 배열_2

---

실습 6-7 단순 삽입 정렬 알고리즘 구현하기

# 단순 삽입 정렬 알고리즘 구현하기

from typing import MutableSequence

def insertion_sort(a: MutableSequence) -> None:
  """단순 삽입 정렬"""
  n = len(a)
  for i in range(1, n):
    j = i
    tmp = a[i]
    while j > 0 and a[j - 1]> tmp:
      a[j] = a[j - 1]
      j -= 1
    a[j] = tmp

if __name__ == '__main__':
  print('단순 삽입 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num  # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))
  
  insertion_sort(x)  # 배열 x를 단순 삽입 정렬

  print('오름차순으로 정렬했습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

단순 삽입 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9

• 이 알고리즘은 서로 떨어져 있는 원소를 교환하지 않으므로 안정적이라고 할 수 있습니다. 원소의 비교 횟수와 교환 횟수는 모두 n² / 2번입니다.
• 단순 삽입 정렬은 셔틀 정렬(shuttle sort)이라고도 합니다.

---

단순 정렬 알고리즘의 시간 복잡도

단순 정렬(버블, 선택, 삽입) 알고리즘의 시간 복잡도는 모두 O(n²)으로 프로그램의 효율이 좋지 않습니다. 이러한 단순 정렬 알고리즘의 개선 방법을 적용한 정렬 알고리즘을 알아보겠습니다.

보충 수업 6-2 이진 삽입 정렬

단순 삽입 정렬은 배열 원소 수가 많아지면 원소 삽입에 필요한 비교 · 교환 비용이 커집니다. 그러나 이진 검색법을 사용하여 삽입 정렬을 하면 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있습니다. 이러한 알고리즘을 이진 삽입 정렬(binary insertion sort)이라고 합니다.

실습 6C-1 이진 삽입 정렬 알고리즘 구현하기

# 이진 삽입 정렬 알고리즘 구현하기

from typing import MutableSequence

def binary_insertion_sort(a: MutableSequence) -> None:
  """이진 삽입 정렬"""
  n = len(a)
  for i in range(1, n):
    key = a[i]
    pl = 0                        # 검색 범위의 맨 앞 원소 인덱스
    pr = i - 1                    # 검색 범위의 맨 끝 원소 인덱스

    while True:
      pc = (pl + pr) // 2         # 검색 범위의 가운데 원소 인덱스
      if a[pc] == key:            # 검색 성공
        break
      elif a[pc] < key:
        pl = pc + 1               # 검색 범위를 뒤쪽 절반으로 좁힘
      else:
        pr = pc - 1               # 검색 범위를 앞쪽 절반으로 좁힘
      if pl > pr:
        break

    pd = pc + 1 if pl <= pr else pr + 1   # 삽입해야 할 위치의 인덱스

    for j in range(i, pd, -1):
      a[j] = a[j - 1]
    a[pd] = key

if __name__ == '__main__':
  print('이진 삽입 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num                # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  binary_insertion_sort(x)        # 배열 x를 이진 삽입 정렬

  print('오름 차순으로 정렬헀습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

---

실습 6C-2 이진 삽입 알고리즘 구현(bisect.insort 사용)

단순 삽입 정렬 알고리즘은 파이썬 표준 라이브러리에서 bisect 모듈의 insort() 함수로 제공합니다. 이미 정렬이 끝난 배열의 상태를 유지하면서 원소를 삽입합니다.

# 이진 삽입 정렬 알고리즘 구현(bisect.insort 사용)

from typing import MutableSequence
import bisect

def binary_insertion_sort(a: MutableSequence) -> None:
  """이진 삽입 정렬(bisect.insort 사용)"""
  for i in range(1, len(a)):
    bisect.insort(a, a.pop(i), 0, i)

if __name__ == '__main__':
  print('이진 삽입 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num                # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  binary_insertion_sort(x)        # 배열 x를 이진 삽입 정렬

  print('오름 차순으로 정렬헀습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

 

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file:
https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습