Preface
오늘은 지난 포스팅에 이어 정렬 알고리즘의 종류 중 하나인 단순 선택 정렬과 단순 삽입 정렬, 이진 삽입 정렬을 공부했다.
단순 선택 정렬은 내가 예상했던 방식으로 코드를 작성하여 큰 어려움 없이 이해할 수 있었지만, 단순 삽입 정렬은 그렇지 않았다.
어떠한 방식으로 정렬이 진행되는 것인지는 금방 이해할 수 있었지만, 이 내용을 코드화하자 생각보다 복잡하여 코드를 한 줄 한 줄 분석한 후 직접 노트에 적어 계산해 본 후에야 코드의 작동 방식을 알 수 있었다.
이진 삽입 정렬도 마찬가지이다.
이진 검색을 하는 부분에서 검색 범위의 맨 끝 원소 인덱스를 i가 아닌 i - 1로 설정한 이유부터 시작하여 j의 값을 굳이 범위로 설정하는 이유 등 곧바로 이해되지 않는 부분들이 있어 한 시간 이상을 고민했던 것 같다.
정렬 파트 부분은 아직 꽤 많이 남았는데, 너무 어려워서 내가 완벽히 이해할 수 있을지 걱정이다.
1. 단순 선택 정렬
- 단순 선택 정렬 : 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘
→ 서로 떨어져 있는 원소를 교환하므로 안정적이지 않다.
- 단순 선택 정렬에서의 교환 과정
1) 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택한다.
2) a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다.
→ n - 1번 반복
- 단순 선택 정렬 코드
from typing import MutableSequence
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]
if __name__ == '__main__':
print('단순 선택 정렬을 수행합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
selection_sort(x)
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
2. 단순 삽입 정렬
- 단순 삽입(셔틀) 정렬 : 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
→ 서로 떨어져 있는 원소를 교환하지 않으므로 안정적이다.
- 단순 삽입 정렬에서의 교환 과정
1) 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입한다.
→ n - 1번 반복
- 종료 조건
1) 정렬된 배열의 왼쪽 끝에 도달한 경우
2) tmp보다 작거나 키값이 같은 원소 a[j - 1]을 발견할 경우
- 계속 조건
1) j가 0보다 큰 경우
2) a[j - 1]의 값이 tmp보다 큰 경우
- 단순 삽입 정렬 코드
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
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
insertion_sort(x)
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
- 이진 삽입 정렬 : 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하는 알고리즘
→ 이진 검색을 통해 원소 삽입 위치를 탐색한다.
- 이진 삽입 정렬 코드
from typing import MutableSequence
def binary_insertion_sort(a: MutableSequence):
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
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
binary_insertion_sort(x)
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
'Algorithm > 자료구조와 함께 배우는 알고리즘(Python)' 카테고리의 다른 글
퀵 정렬 (0) | 2022.01.08 |
---|---|
셸 정렬 (0) | 2022.01.06 |
정렬 알고리즘, 버블 정렬 (0) | 2022.01.02 |
하노이의 탑, 8퀸 문제 (0) | 2021.12.29 |
재귀 알고리즘의 기본, 재귀 알고리즘 분석 (0) | 2021.10.25 |
댓글