[알고리즘] 버블 정렬

버블 정렬은, 배열 내 이웃한 원소들을 비교함으로써 정렬하는 알고리즘이다.

어느 배열 a가 n개의 원소를 가진다면, a[n - 1]과 a[n - 2], ... , a[1]과 a[0]을 순차적으로 비교한다.

버블 정렬은 안정적인 알고리즘이며, 시간 복잡도는 O(N^2)이다. (교재 p224 참고)

 

# 버블 정렬 알고리즘 구현하기

from typing import MutableSequence

def bubble_sort(a: MutableSequence) -> None:
    """버블 정렬"""
    
    n = len(a)
    
    for i in range(n - 1): # i의 범위: 0 ~ n - 2
        for j in range(n - 1, i, -1): # 11 ~ 13행: Pass 과정
            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]}')