버블 정렬이란?
- 이웃한 두 원소의 대소 관계를 비교하고, 교환을 반복하는 알고리즘(=단순 교환 정렬)
- 액체 속의 공기 방울이 가벼워서 위로 보글보글 올라오는 모습에 착안해서 붙인 이름
오름차순 정렬하는 버블 정렬의 첫 번째 패스 진행 과정은 다음과 같다.
1) 오른쪽 끝에 있는 두 원소 9와 8에 주목한다.
2) 9와 8의 위치를 교환한다.
3) 다음 원소인 1과 8에 주목한다.
4) 1과 8의 위치는 교환하지 않는다.
원소 수가 n인 배열에서 n - 1번 비교 & 교환을 하면 가장 작은 원소인 1이 맨 앞으로 이동한다. 이러한 과정을 패스라고 한다.
위와 같이 패스를 한 번 수행할 때마다 정렬할 대상은 1개씩 줄어든다. 그러므로 두 번째 패스의 비교 횟수는 첫 번째 패스보다 1번 적은 n - 2번이다. 패스를 k번 수행하면 맨 앞부터 k개 원소가 정렬되고, 모든 정렬이 끝나려면 패스를 n - 1번 수행해야 한다.
(수행하는 패스 횟수가 n번이 아니라 n - 1번인 이유는 n - 1개 원소의 정렬이 끝나면 마지막 원소는 이미 끝에 놓이기 때문)
아래 코드는 버블 정렬 알고리즘으로 작성된 코드
# 버블 정렬 알고리즘 구현하기
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]}')
실행 결과
버블 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9
Process finished with exit code 0
위 코드는 배열의 맨 끝(우측)에서 맨 앞(좌측)을 향해 스캔하기 때문에 j의 시작값은 n - 1이다.
두 원소 a[j - 1]과 a[j]의 값을 비교해서 앞쪽 값(좌측)이 뒷쪽 값(우측)보다 크면 교환한다.
* 버블 정렬은 이와 같이 서로 이웃한 원소만 교환하기 때문에 안정적이다.
아래 코드는 원소를 어떤 순서로 비교하고 교환하는 지 구체적인 결과로 드러내주는 코드이다.
# 버블 정렬 알고리즘 구현하기(정렬 과정을 출력)
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]}')
실행 결과
버블 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
패스 1
6 4 3 7 1 9 + 8
6 4 3 7 1 - 8 9
6 4 3 7 + 1 8 9
6 4 3 + 1 7 8 9
6 4 + 1 3 7 8 9
6 + 1 4 3 7 8 9
1 6 4 3 7 8 9
패스 2
1 6 4 3 7 8 - 9
1 6 4 3 7 - 8 9
1 6 4 3 - 7 8 9
1 6 4 + 3 7 8 9
1 6 + 3 4 7 8 9
1 3 6 4 7 8 9
패스 3
1 3 6 4 7 8 - 9
1 3 6 4 7 - 8 9
1 3 6 4 - 7 8 9
1 3 6 + 4 7 8 9
1 3 4 6 7 8 9
패스 4
1 3 4 6 7 8 - 9
1 3 4 6 7 - 8 9
1 3 4 6 - 7 8 9
1 3 4 6 7 8 9
패스 5
1 3 4 6 7 8 - 9
1 3 4 6 7 - 8 9
1 3 4 6 7 8 9
패스 6
1 3 4 6 7 8 - 9
1 3 4 6 7 8 9
비교를 21번 했습니다.
교환을 8번 했습니다.
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9
Process finished with exit code 0
이 코드의 입력값에 원소 수(num) = 7, 값(x[i]) = 6, 4, 3, 7, 1, 9, 8를 입력하게 되면 비교를 21번, 교환을 8번 한 후 정렬이 끝난다.
다음 코드는 위 코드를 개선하여 교환 횟수에 따른 중단 방식을 적용한 코드이다.
# 버블 정렬 알고리즘 구현하기(알고리즘의 개선 1)
from typing import MutableSequence
def bubble_sort(a: MutableSequence) -> None:
"""버블 정렬(교환 횟수에 따른 중단)"""
ccnt = 0 # 비교 횟수
scnt = 0 # 교환 횟수
n = len(a)
for i in range(n - 1):
print(f'패스 {i + 1}')
exchng = 0 # 패스에서 교환 횟수
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],
exchng += 1
for m in range(0, n - 1):
print(f'{a[m]:2}', end=' ')
print(f'{a[n - 1]:2}')
if exchng == 0:
break
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(x) # 배열 x를 버블 정렬
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
실행 결과
버블 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
패스 1
6 4 3 7 1 9 + 8
6 4 3 7 1 - 8 9
6 4 3 7 + 1 8 9
6 4 3 + 1 7 8 9
6 4 + 1 3 7 8 9
6 + 1 4 3 7 8 9
1 6 4 3 7 8 9
패스 2
1 6 4 3 7 8 - 9
1 6 4 3 7 - 8 9
1 6 4 3 - 7 8 9
1 6 4 + 3 7 8 9
1 6 + 3 4 7 8 9
1 3 6 4 7 8 9
패스 3
1 3 6 4 7 8 - 9
1 3 6 4 7 - 8 9
1 3 6 4 - 7 8 9
1 3 6 + 4 7 8 9
1 3 4 6 7 8 9
패스 4
1 3 4 6 7 8 - 9
1 3 4 6 7 - 8 9
1 3 4 6 - 7 8 9
1 3 4 6 7 8 9
비교를 18번 했습니다.
교환을 8번 했습니다.
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9
Process finished with exit code 0
새로 추가한 변수 exchng는 패스를 시작하기 전 0으로 초기화되고, 원소를 교환할 때마다 1씩 증가시킨다.
하나의 패스를 마친 상태에서는 exchng값은 패스에서의 교환 횟수와 같아지게 된다.
이 코드도 마찬가지로 입력값에 원소 수(num) = 7, 값(x[i]) = 6, 4, 3, 7, 1, 9, 8를 입력한 후 이전 코드와 비교해본다.
비교를 18번, 교환을 8번 한 후 정렬이 끝난다. 이전 코드보다 더 효율적으로 수행되었다.
다음 코드는 이미 정렬된 원소를 제외한 나머지만 비교, 교환하도록 스캔 범위를 제한하는 방법으로 개선한 프로그램이다.
# 버블 정렬 알고리즘 구현하기(알고리즘의 개선 2)
from typing import MutableSequence
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
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]}')
실행 결과
버블 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 1
x[1]: 3
x[2]: 9
x[3]: 4
x[4]: 7
x[5]: 8
x[6]: 6
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9
Process finished with exit code 0
실제로 위의 코드를 실행시켜 원소 수는 7, 배열 값에는 [1, 3, 9, 4, 7, 8, 6]을 입력 하면 가장 적은 횟수를 비교하여 정렬을 수행한다.
하지만 이제까지 살펴본 코드 모두 [9, 1, 3, 4, 6, 7, 8]을 대입하면 전부 21번 비교하고 6번 교환을 하기때문에 개선이 무의미해진다.
이러한 코드를 개선하기 위해 다음 글에서는 셰이커 정렬을 알아본다.
'자료구조, 알고리즘 입문 > 정렬 알고리즘' 카테고리의 다른 글
| [정렬 알고리즘] 퀵 정렬 (3) | 2024.09.22 |
|---|---|
| [정렬 알고리즘] 단순 삽입 정렬(셔틀 정렬), 이진 삽입 정렬 (0) | 2022.05.26 |
| [알고리즘] 단순 선택 정렬 (0) | 2022.05.23 |
| [알고리즘] 셰이커 정렬, 파이썬 내장 함수 (0) | 2022.05.19 |
| [알고리즘] 정렬 알고리즘 개요 (0) | 2022.05.18 |