[알고리즘] Bubble sort : 버블 소트
정렬 포스트 중 첫 번째 포스트 버블 소트입니다.
버블 소트 (Bubble sort)
버블 소트는 정렬 알고리즘 중에서 가장 간단하면서, 컴퓨팅적 사고 관점에서 가장 직관적인 알고리즘이라고 생각합니다. 이제 버블 소트에 대해서 알아보도록 하겠습니다.
개념
버블 소트는 두 인접한 원소를 비교하여 큰 수를 뒤로 보내는 방법으로 정렬하는 알고리즘입니다. 배열을 세로로 생각하면, 이 과정에서 큰 수 들이 위로 가기 때문에 버블이라고 이름을 지은 것 같습니다.
정렬하는 과정을 더 자세히 살펴보겠습니다. 길이가 n인 1차원 배열이 있다고 가정합시다. 우리의 목표는 이 배열을 오름차순으로 정렬하는 것입니다.
배열의 i 번째의 원소와 i+1 번째 원소를 비교하고 더 큰 원소를 i+1 번째에, 작은 원소를 i 번째로 자리를 지정해줍니다.
첫 번째 원소와 두 번째 원소를 비교, 그 다음 두 번째 원소와 세 번째 원소, 그 다음 세 번째 원소와 네 번째 원소, … 이런 과정들을 반복하면서 정렬을 하는 것입니다.
버블 소트 방식으로 실제 정렬을 해보면서 코드를 어떻게 짤 지 구상해보겠습니다.
예시
다음과 같이 길이가 5인 배열이 있습니다.
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 5 | 4 | 3 | 2 | 1 |
버블 소트로 정렬해 봅시다
시행 1)
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 4 |
5 |
3 | 2 | 1 |
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 4 | 3 |
5 |
2 | 1 |
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 4 | 3 | 2 |
5 |
1 |
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 4 | 3 | 2 | 1 |
5 |
이렇게 배열 끝까지 원소 비교를 하는 첫 시행을 거치면 가장 큰 수가 배열의 끝에 온다는 것을 알 수 있습니다. 아직 정렬이 다 되지 않았으니 계속 하겠습니다.
시행 2)
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 3 |
4 |
2 | 1 | 5 |
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 3 | 2 |
4 |
1 | 5 |
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 3 | 2 | 1 |
4 |
5 |
5는 원소 중 가장 큰 값이므로 비교하지 않아도 됩니다. 두 번째 시행을 하면 두 번째로 큰 원소가 배열 끝에서 두 번째에 온다는 것을 알 수 있습니다. 마저 정렬을 해보겠습니다.
시행 3)
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 2 |
3 |
1 | 4 | 5 |
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 2 | 1 |
3 |
4 | 5 |
시행 4)
| 위치 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소 | 1 |
2 |
3 | 4 | 5 |
이렇게 정렬이 끝났습니다.
버블 소트는 뒤에서부터 정렬된 값이 저장이되고, 시행을 n-1번 하면 배열이 전부 정렬됩니다.
n번이 아니라 n-1번인 이유는 배열의 두 번째로 작은 원소를 결정지으면 가장 작은 원소는 자동적으로 첫 번째에 위치하므로 연산을 더 할 필요가 없기 때문입니다.
또 정렬되지 않은 값만 정렬해주면 되므로 (n-시행횟수) 의 원소까지만 비교를 해주면 됩니다.
분석
이 알고리즘을 분석해보겠습니다. 최악의 경우는 사실 위의 예시처럼 내림차순으로 정렬되어 있을 경우 입니다. 각 시행에서의 비교 횟수를 다 더하면 4+3+2+1이 됩니다.
일반화를 시키면, 길이가 n인 배열에서의 비교 횟수는 $(n-1)+(n-2)+…+2+1=\frac{n(n-1)}{2}$이고 빅오 노테이션으로 표현하면 $O(n^2)$입니다.
- 시간 복잡도 : $O(n^2)$
코드 (Python)
간단한 코드
배열 A를 입력받는 함수 코드입니다.
def bubble_sort(A):
n=len(A)-1
for i in range(n):
for j in range(n-i):
if A[j]>=A[j+1]:
A[j],A[j+1]=A[j+1],A[j]
# 각 시행 단계의 결과 출력
print("시행",i+1,":",A)
return A
정말 잘 정렬이 되는 지 확인해봅시다.
A=[5,4,3,2,1]
A=bubble_sort(A)
위 코드를 실행시키면 아래의 결과를 얻을 수 있습니다.
잘 정렬이 되었습니다. 그런데 위의 코드는 문제점이 있습니다. 배열이 [3,1,5,2,4]인 경우를 생각해보겠습니다. 이 배열의 경우 시행을 2번 하면 정렬이 끝나지만, 위의 코드는 시행 4번을 다 합니다. 따라서 아래는 정렬이 다 되면 연산을 멈추는 조금 더 개선된 코드를 보겠습니다.
개선된 코드
사람은 눈으로 보면 정렬이 된 것을 알 수 있습니다. 컴퓨터는 정렬이 다 된 것을 어떻게 인식할 수 있을까요? 시행 내에서 자리 교환이 이루어지지 않으면 정렬이 다 되었다고 인식하고 연산을 멈추는 코드가 아래 코드입니다.
def bubble_sort(A):
n=len(A)-1
for i in range(n):
swapped=False
for j in range(n-i):
if A[j]>=A[j+1]:
A[j],A[j+1]=A[j+1],A[j]
# 자리 교환이 일어남
swapped=True
# 각 시행 단계의 결과 출력
print("시행",i+1,":",A)
if not swapped:
break
return A
확인을 해보겠습니다.
B=[3,1,5,2,4]
B=bubble_sort(B)
위 코드를 실행시키면 아래와 같은 결과를 얻을 수 있습니다.
시행 3에서 자리 교환이 일어나지 않았으므로 다음 연산을 진행하지 않습니다. 이런 방식으로 연산량을 줄일 수 있습니다.
참고 사이트 : https://bowbowbow.tistory.com/10