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

출처: Do it! 자료구조와 함께 배우는 알고리즘 입문

 

버블정렬

버블정렬은 이웃한 두 원소의 대소관계를 비교하여 필요에 따라 교환을 반복한다.

7개의 원소 6,4,3,7,1,9,8를 대입했다.

패스는 비교 교환하는 과정을 말하는데 패스 1은 첫바퀴 정렬을 의미한다. 

첫번째 패스 시 , 정렬 완료 전까지 n-1번의 정렬과정을 거친다. 가장 작은 원소 1이 맨 앞으로 이동한다.

두번째 패스 시 정렬 완료 전까지 n-2의 정렬과정을 거치고, 두번째로 작은 원소 3이 두번째 위치로 이동한다. 

 

버블정렬 구조는 다음과 같다.

def bubble_sort(a: MutableSequence) -> None:
    """버블 정렬"""
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1, i, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]

배열의 맨끝에서 맨 앞을 향해 스캔하므로 j의 시작값은 n-1이다. 이때 a[j-1]과 a[j]를 비교하여 앞쪽 값이 뒤쪽 값보다 크면 교환해준다. 뒤에서 앞으로 가기때문에 j는 1씩 감소한다. j가 i+1이 될때까지 비교 교환한다. 

원소를 비교하는 횟수는 첫번째는 (n-1)번, 두번째는 (n-2)번,,, 이므로 합계는다음과 같다.

(n-1)+(n-2)+ ... + 1= n(n-1)/2

실제 원소 교환 횟수는 배열의 원솟값에 따라 영향을 받으므로 평균값은 전체의 절반인 n(n-1)/4 이다. 

 

버블 정렬 첫번째 코드를 출력하면 다음과 같다. 

from typing import MutableSequence

def bubble_sort_verbose(a: MutableSequence) -> None:
    """버블 정렬(정렬 과정을 출력)"""
    ccnt = 0  # 비교 횟수
    scnt = 0  # 교환 횟수
    n = len(a)
    for i in range(n - 1):
        print(f'패스 {i + 1}')
        for j in range(n - 1, i, -1):
            for m in range(0, n - 1):
               print(f'{a[m]:2}' + ('  ' if m != j - 1 else
                                    ' +' if a[j - 1] > a[j] else ' -'), 
                                    end='')
            print(f'{a[n - 1]:2}')
            ccnt += 1
            if a[j - 1] > a[j]:
                scnt += 1
                a[j - 1], a[j] = a[j], a[j - 1]
        for m in range(0, n - 1):
           print(f'{a[m]:2}', end='  ')
        print(f'{a[n - 1]:2}')
    print(f'비교를 {ccnt}번 했습니다.')
    print(f'교환을 {scnt}번 했습니다.')

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

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

    bubble_sort_verbose(x)  # 배열 x를 버블 정렬

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

비교를 21번 했습니다.

교환을 8번 했습니다.

오름차순으로 정렬했습니다.

 

패스 3과 패스 4를 보면, 정렬이 완료된 앞 원소와 이미 정렬이 된 원소를 교환하지 않는다. 

어떤 패스의 원소 교환 횟수가 0이면, 모든 원소가 정렬을 완료한 경우이므로 그 이후의 패스를 중단한다.

코드를 개선하면 다음과 같다. 

def bubble_sort(a: MutableSequence) -> None:
    """버블 정렬(교환 횟수에 따른 중단)"""
    n = len(a)
    for i in range(n - 1):
        exchng = 0  # 패스에서 교환 횟수
        for j in range(n - 1, i, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                exchng += 1
        if exchng == 0:
            break

exchng변수를 추가해서 교환을 실행할 때마다 1씩 더해준다. 교환되는 횟수가 0이면, break를 걸어서 함수 실행을 종료시킨다. 

더이상교환이 되지 않는 패스 4에서 교환이 중단된다. 이러한 방법으로 21번에서 18번으로 교환횟수가 감소했다.

버블정렬 알고리즘 개선 2

마지막 교환 9와 4를 교환한 이후 교환이 이루어지지 않는다. 이미 정렬된 원소를 제외한 나머지만 비교하도록 스캔 범위를 개선한다.

def bubble_sort(a: MutableSequence) -> None:
    """버블 정렬(스캔 범위를 제한)"""
    n = len(a)
    k = 0
    while k < n - 1:
        last = n - 1
        for j in range(n - 1, k, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                last = j
        k = last

 last는 각 패스에서 마지막으로 교환한 두 원소 가운데 오른쪽 원소(여기선 4의 인덱스 3)을 저장한다. 교환할때마다 오른쪽 원소의 인덱스값을 last에 대입한다. 다음 수행할 패스의 스캔범위를 a[k]로 제한한다. 

다음 패스에서 마지막으로 비교할 두 원소는 a[k]과 a[k+1]이다.

셰이커 정렬

홀수번째 패스에서는 가장 작은 원소를 맨앞으로 이동시키고, 짝수패스에서는 가장 큰 원소를 맨 뒤로 이동시킨다. 

def shaker_sort(a: MutableSequence) -> None:
    """셰이커 정렬"""
    left = 0 #스캔 범위의 첫 원소 인덱스
    right = len(a) - 1 #스캔 범위의 마지막 인덱스
    last = right
    while left < right: 
        for j in range(right, left, -1): #홀수 패스 맨뒤에서 맨앞으로 캔
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                last = j
        left = last

        for j in range(left, right): #짝수 패스 맨앞에서 맨뒤로 스캔
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                last = j
        right = last

단순 선택 정렬

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
        print(i,j)
        a[i], a[min] = a[min], a[i]  # 정렬 할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환
        print(f'단계 {i+1}: {a},')  # 현재 단계에서 배열의 상태를 출력

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

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

    selection_sort(x)  # 배열 x를 단순 선택 정렬

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

입력원소 6483197

맨 앞 인덱스(6)와 가장 작은 원소(1)과 비교하여 맨 앞 인덱스 자리에 1을 배치한다.

이런식으로 인덱스 n +=1값과 min(a,n) 값을 비교하여 교환이 이루어진다. 

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

 

단순 삽입 정렬

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다. 

6 4 1 7 3 9 8 원소를 대입했다고 가정하자. 

원소 3을 앞 원소와 비교해서 3보다 작은 값을 만날때까지 이웃한 왼쪽 원소를 대입한다. 

배열에 어떤값을 알맞은 위치에 삽입하는 과정은 다음과 같다.

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

정렬된 배열의 왼쪽끝에 도달하거나 tmp(여기서3)보다 작거나  키값이 같은 원소 aj[j-1]을 발견한 경우 종료하고

j가 0보다 크거나 a[j-1]의 값이 tmp(3)보다 큰경우 작업을 계속한다. 

원소의 비교횟수와 교환횟수는 모드 (n^2)/2번이다.