정렬 알고리즘, 버블 정렬

Preface

 

이번 장에선 정렬 알고리즘이란 무엇인지에 관한 내용과 그 종류 중 하나인 버블 정렬 및 버블 정렬에 약간의 변화를 준 셰이커 정렬을 공부했다.

 

코드를 작성할 땐 아무 생각 없이 책에 나온 방식대로 진행하게 되지만, 해당 코드를 완성하면 기존의 코드에 능률성을 더한 새로운 코드 작성을 요구한다.

 

이전부터 코드를 작성할 때 어떻게 해야 더욱 효율적인 코드를 작성할 수 있을지를 고민하자고 생각은 하지만, 막상 공부를 하다 보면 그게 마음대로 되지 않는다.

 

내일부턴 책에 있는 코드를 그대로 따라 작성하기 전에 해당 문제를 해결할 방법을 미리 고민해 본 후 책과 비교하며 코드를 짤 생각이다.

 

또, 알고리즘 공부를 시작한 뒤로 진도를 나가는 데 시간이 너무 오래 걸리는데, 내 공부 방식이 맞는 것인지, 너무 미련하게 공부하고 있는 것은 아닌지 고민이 된다.

---

 

1. 정렬 알고리즘

 

 

- 정렬 : 다양한 키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업

1) 오름차순 정렬 : 값이 작은 데이터를 앞쪽에 늘어놓는 것

2) 내림차순 정렬 : 값이 큰 데이터를 앞쪽에 늘어놓는 것

3) 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용하는 알고리즘

4) 외부 정렬 : 정렬할 데이터가 많아 하나의 배열에 저장할 수 없는 경우 사용하는 알고리즘

→ 별도의 작업용 파일이 필요하며 알고리즘도 복잡함

 

 

- 안정적인 정렬 알고리즘 : 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것

 

 

- 정렬 알고리즘의 핵심 키워드

1) 교환

2) 선택

3) 삽입

 

---

 

2. 버블 정렬

 

 

- 버블 정렬 : 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘

→ 서로 이웃한 두 원소만 교환하므로 안정적이다.

 

 

- 패스(pass) : 일련의 비교·교환 과정

1) 패스를 한 번 수행할 때마다 정렬할 대상은 1개씩 줄어듦

2) 모든 정렬이 끝나려면 패스를 n - 1번 수행해야 함

 

 

- 버블 정렬 코드

from typing import MutableSequence


def bubble_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(n - 1):
        # 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]


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

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

    bubble_sort(x)

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

 

 

- 버블 정렬 교환 과정 출력 코드

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

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

    bubble_sort_verbose(x)

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

 

 

- 버블 정렬에 교환 횟수에 따른 중단 방식을 적용한 코드

from typing import MutableSequence


def bubble_sort(a: MutableSequence) -> None:
    ccnt = 0  # 비교 횟수
    scnt = 0  # 교환 횟수
    n = len(a)
    for i in range(n - 1):
        exchange = 0  # 교환 횟수
        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]
                exchange += 1
        for m in range(0, n - 1):
            print(f'{a[m]:2}', end='  ')
        print(f'{a[n - 1]:2}')
        if exchange == 0:
            break
            # 교환 횟수가 0이면 for 문을 탈출하여 비교 횟수를 줄임
    print(f'비교를 {ccnt}번 했습니다.')
    print(f'교환을 {scnt}번 했습니다.')


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

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

    bubble_sort(x)

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

 

 

- 특정한 원소 이후에 교환하지 않는다면 그 원소 앞에 있는 원소는 이미 정렬을 마친 상태이다.

 

 

- 버블 정렬에 스캔 범위를 제한하는 방식을 적용한 코드

from typing import MutableSequence


def bubble_sort(a: MutableSequence) -> None:
    ccnt = 0  # 비교 횟수
    scnt = 0  # 교환 횟수
    n = len(a)
    k = 0
    t = 1
    while k < n - 1:
        last = n - 1
        print(f'패스 {t}')
        for j in range(n - 1, k, -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]
                last = j
        for m in range(0, n - 1):
            print(f'{a[m]:2}', end='  ')
        print(f'{a[n - 1]:2}')
        k = last
        t += 1
    print(f'비교를 {ccnt}번 했습니다.')
    print(f'교환을 {scnt}번 했습니다.')


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

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

    bubble_sort(x)

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

 

 

- 셰이커 정렬 : 홀수 패스에선 가장 작은 원소를 맨 앞으로, 짝수 패스에선 가장 큰 원소를 맨 뒤로 이동시켜 패스의 스캔 방향을 번갈아 바꾸는 알고리즘

→ 양방향 버블 정렬, 칵테일 정렬, 칵테일 셰이커 정렬과 같은 단어로 사용된다.

 

 

- 셰이커 정렬 코드

from typing import MutableSequence


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
        # 나열된 원소를 맨 앞에서 맨 뒤로 스캔
        # ...생략...