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

단순 선택 정렬의  정의

 

단순 선택 정렬(straight selection sort)은 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘이다. 다음은 단순 선택 정렬의 과정이다.

 

 

아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택하고, 아직 정렬하지 않은 부분의 맨 앞 원소와 교환하는 작업을 반복한다.

이 과정을 n - 1번 반복하면 정렬하지 않은 부분이 없어지면서 전체 정렬을 완료한다. 알고리즘의 개요는 다음과 같다.

 

for i in range(n - 1):
    min    # a[i], ... a[n-1]에서 키 값이 가장 작은 원소의 인덱스
    a[i]와 a[min]의 값을 교환

 

<code>

def selection_sort(a):
    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]    # 정렬할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환

 

단순 선택 정렬 알고리즘의 원솟값을 비교하는 횟수는 (n^2 - n) / 2번이다.

하지만 이 알고리즘은 서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않다.

안정적이지 않은 정렬

---

 

단순 삽입 정렬의 정의

 

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

 

 

이때 i를 1, 2, ... n - 1까지 1씩 증가시키면서 인덱스 i의 원소를 꺼내 알맞은 위치에 삽입한다. 알고리즘의 개요는 다음과 같다.

 

for i in range(1, n):
    tmp <- a[i]를 넣는다.
    tmp를 a[0], ... a[i - 1]의 알맞은 위치에 삽입한다.

 

<code>

def insertion_sort(a):
    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]}')

 

이 알고리즘은 서로 떨어져 있는 원소를 교환하지 않으므로 안정적이라고 할 수 있다. 원소의 비교 횟수와 교환 횟수는 모두 n^2 / 2번이다.

 

이전까지 다룬 버블, 선택, 삽입 알고리즘의 시간 복잡도는 모두 O(n^2)으로 효율이 좋지 않다.

---

이진 삽입 정렬

 

단순 삽입 정렬은 배열 원소 수가 많아지면 원소 삽입에 필요한 비교-교환 비용이 커진다. 그러나 이진 검색법을 사용하여 삽입 정렬을 하면 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있다.

 

<code>

def binary_insertion_sort(a):
    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]}')

 

 

** 단순 삽입 정렬 알고리즘은 파이썬 표준라이브러리 bisect 모듈의 insort() 함수로 제공한다.

 

<code>

import bisect

def binary_insertion_sort(a):
    for i in range(1, len(a)):
        bisect.insort(a, a.pop(i), 0, i)