단순 선택 정렬, 단순 삽입 정렬

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]}')