단순 선택 정렬
단순 선택 정렬이란 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘입니다.
아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택하고, 정렬하지 않은 부분의 맨 앞 원소와 교환합니다.
def selection_sort(a: MutableSequence) -> None:
n = len(a)
for i in range(n - 1):
min = i
for j in range(i+1, n):
if a[j] < a[min]:
min = j
a[i], a[min] = a[min], a[i]
예시: [6, 4, 1, 7, 3, 9, 8]
① 먼저 배열에서 가장 작은 원소와 아직 정렬하지 않은 부분(배열 전체)의 첫번째 원소와 교환합니다.
→ [1, 4, 6, 7, 3, 9, 8]
② 다음은 정렬되지 않은 배열의 원소 중(두 번째 원소부터) 가장 작은 원소와 아직 정렬하지 않은 부분의 첫번째 원소와 교환합니다.
→ [1, 3, 6, 7, 4, 9, 8]
③ 이후 계속 같은 작업을 반복합니다.
단순 삽입 정렬의 시간복잡도는 O(n^2)입니다.
그렇지만 이는 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않습니다. 그럼 안정적이지 않은 정렬이란?
정렬 후에도 그 정렬이 유지된다는 보장이 없다는 것입니다.
단순 삽입 정렬
단순 삽입 정렬은 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘입니다. 단순 선택 정렬과 비슷하지만 단순 선택 정렬과 다르게 가장 작은 원소를 선택하지 않습니다.
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] # 오른쪽으로 shift
j -= 1
a[j] = tmp
예시: [6, 4, 1, 7, 3, 9, 8]
① 먼저 배열의 두 번째 원소부터 주목한 후, 앞의 원소랑 비교해서 6보다 작으므로 6을 오른쪽으로 옮긴 후 그 자리에 삽입합니다.
→ [4, 6, 1, 7, 3, 9, 8]
② 다음은 배열의 세 번째 원소를 주목한 후, 앞의 4, 6을 오른쪽으로 옮긴 후 맨 앞에 삽입합니다.
→ [1, 4, 6, 7, 3, 9, 8]
③ 이후 계속 같은 작업을 반복합니다.
이 알고리즘은 떨어져 있는 원소를 교환하지 않으므로, 안정적이라고 할 수 있습니다. 마찬가지로 시간 복잡도는 O(n^2)입니다.
또한 단순 삽입 정렬 알고리즘은 파이썬 표준 라이브러리에서 bisect 모듈의 insort() 함수로 제공합니다.
이진 삽입 정렬(단순 삽입 정렬 개선 알고리즘)
단순 삽입 정렬에서는 i를 증가시키면서 왼쪽의 정렬된 부분에서 a[i]가 들어갈 곳을 찾아서 집어넣는 작업을 해나가는데, 이때 '정렬된 부분에서 a[i]가 삽입될 곳을 찾는 작업'을 이진 검색법을 사용하여 찾음으로써 비용을 줄일 수 있습니다. 즉, 비교에 대한 시간복잡도가 O(n^2)에서 O(nlogn)으로 개선됩니다.
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
if pl <= pr:
pd = pc + 1
else:
pd = pr + 1
for j in range(i, pd, -1):
a[j] = a[j - 1]
a[pd] = key