[자료구조] 정렬 알고리즘 - 버블 정렬

1. 버블정렬

 

1.1. 개념

• 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 한다.

1.2. 과정

• 오른쪽 맨 끝에 있는 두 원소 9와 8에 주목한다. 이때 배열을 오름차순으로 정렬한다면, 왼쪽의 값(9)이 오른쪽의 값(8)과 같거나 작아야 한다.
• 9와 8을 교환하고 다음 비교 대상인 1과 8에 주목한다. 1은 8보다 작으므로 교환할 필요가 없다.
• 원소 수가 n인 배열에서 n-1번 비교, 교환을 하면 가장 작은 원소인 1이 맨 앞으로 이동한다. 이러한 일련의 비교, 교환 과정을 패스라고 한다.
  

  

• 첫 번째 패스로 가장 작은 원소의 정렬이 끝나고 다음 작은 원소를 정렬하기 위해 비교, 교환하는 패스는 아래와 같다. 
  

  

• 이처럼 패스를 한번 종료할 때마다 정렬한 대상은 1개씩 줄어든다. 모든 정렬이 끝나려면 패스를 n-1번 수행해야 한다.

 

1.3. 코드구현

from typing import MutableSequence


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]


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(x)  # 배열 x를 버블 정렬

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