버블정렬(Bubble Sort)은 선택 정렬(Select Sort)과 유사한 알고리즘이다.
서로 인접한 두 원소를 비교하여 조건에 맞거나, 맞지 않을 경우 자리를 교환하며 정렬하는 알고리즘이다.
이름의 유래로는 정렬 과정에서 원소의 이동이 거품과 비슷한 모습을 보인다고 해서 지어졌다고 한다.
데이터: [4, 6, 2, 7, 8, 5, 0, 1]
[4, 2, 6, 7, 5, 0, 1, 8]
[2, 4, 6, 5, 0, 1, 7, 8]
[2, 4, 5, 0, 1, 6, 7, 8]
[2, 4, 0, 1, 5, 6, 7, 8]
[2, 0, 4, 1, 5, 6, 7, 8]
[0, 1, 2, 4, 5, 6, 7, 8]
[4, 6, 2, 7, 8, 5, 0, 1]
==> [0, 1, 2, 4, 5, 6, 7, 8]
datas = [4, 6, 2, 7, 8, 5, 0, 1]
for i in range(len(datas)):
for j in range(1, len(datas)-i):
if datas[j-1] > datas[j]:
datas[j-1], datas[j] = datas[j], datas[j-1]
print(f"결과: {datas}")
datas = [4, 6, 2, 7, 8, 5, 0, 1]
# 0번 부터 시작함
for i in range(len(datas)):
# (0,1), (1,2), (2,3)... 이런식으로 비교함
# 다음에 비교 다하면 i + 1되면서
# (1,2), (2,3), (3,4)... 비교함
for j in range(1, len(datas)-i):
# 조건을 만족(이전 위치가 현재 위치보다 크면)하면 위치 변경
if datas[j-1] > datas[j]:
print(f"{datas[j-1]} 이(가) {datas[j]} 보다 큼으로 변경")
print(datas, '=>', end=' ')
datas[j-1], datas[j] = datas[j], datas[j-1]
print(datas)
print()
print(f"{i+1}회전: {datas}")
print()
# 결과
print(f"결과: {datas}")
6 이(가) 2 보다 큼으로 변경
[4, 6, 2, 7, 8, 5, 0, 1] => [4, 2, 6, 7, 8, 5, 0, 1]
8 이(가) 5 보다 큼으로 변경
[4, 2, 6, 7, 8, 5, 0, 1] => [4, 2, 6, 7, 5, 8, 0, 1]
8 이(가) 0 보다 큼으로 변경
[4, 2, 6, 7, 5, 8, 0, 1] => [4, 2, 6, 7, 5, 0, 8, 1]
8 이(가) 1 보다 큼으로 변경
[4, 2, 6, 7, 5, 0, 8, 1] => [4, 2, 6, 7, 5, 0, 1, 8]
1회전: [4, 2, 6, 7, 5, 0, 1, 8]
4 이(가) 2 보다 큼으로 변경
[4, 2, 6, 7, 5, 0, 1, 8] => [2, 4, 6, 7, 5, 0, 1, 8]
7 이(가) 5 보다 큼으로 변경
[2, 4, 6, 7, 5, 0, 1, 8] => [2, 4, 6, 5, 7, 0, 1, 8]
7 이(가) 0 보다 큼으로 변경
[2, 4, 6, 5, 7, 0, 1, 8] => [2, 4, 6, 5, 0, 7, 1, 8]
7 이(가) 1 보다 큼으로 변경
[2, 4, 6, 5, 0, 7, 1, 8] => [2, 4, 6, 5, 0, 1, 7, 8]
2회전: [2, 4, 6, 5, 0, 1, 7, 8]
6 이(가) 5 보다 큼으로 변경
[2, 4, 6, 5, 0, 1, 7, 8] => [2, 4, 5, 6, 0, 1, 7, 8]
6 이(가) 0 보다 큼으로 변경
[2, 4, 5, 6, 0, 1, 7, 8] => [2, 4, 5, 0, 6, 1, 7, 8]
6 이(가) 1 보다 큼으로 변경
[2, 4, 5, 0, 6, 1, 7, 8] => [2, 4, 5, 0, 1, 6, 7, 8]
3회전: [2, 4, 5, 0, 1, 6, 7, 8]
5 이(가) 0 보다 큼으로 변경
[2, 4, 5, 0, 1, 6, 7, 8] => [2, 4, 0, 5, 1, 6, 7, 8]
5 이(가) 1 보다 큼으로 변경
[2, 4, 0, 5, 1, 6, 7, 8] => [2, 4, 0, 1, 5, 6, 7, 8]
4회전: [2, 4, 0, 1, 5, 6, 7, 8]
4 이(가) 0 보다 큼으로 변경
[2, 4, 0, 1, 5, 6, 7, 8] => [2, 0, 4, 1, 5, 6, 7, 8]
4 이(가) 1 보다 큼으로 변경
[2, 0, 4, 1, 5, 6, 7, 8] => [2, 0, 1, 4, 5, 6, 7, 8]
5회전: [2, 0, 1, 4, 5, 6, 7, 8]
2 이(가) 0 보다 큼으로 변경
[2, 0, 1, 4, 5, 6, 7, 8] => [0, 2, 1, 4, 5, 6, 7, 8]
2 이(가) 1 보다 큼으로 변경
[0, 2, 1, 4, 5, 6, 7, 8] => [0, 1, 2, 4, 5, 6, 7, 8]
6회전: [0, 1, 2, 4, 5, 6, 7, 8]
7회전: [0, 1, 2, 4, 5, 6, 7, 8]
8회전: [0, 1, 2, 4, 5, 6, 7, 8]
결과: [0, 1, 2, 4, 5, 6, 7, 8]
시간 복잡도는 (n-1) + (n-2) + (n-3) + ... + 2 + 1
==> n (n-1) / 2
이므로 O(n^2)
이다.
또한 버블 정렬은 정렬을 했던 안했던 비교 작업을 수행하기 때문에 최선, 평균, 최악 모두 같은 O(n^2)
의 시간이 걸린다.
주어진 배열 안에서 교환이 이루어지므로 O(n)
이다.
a, b = b, a
를 통해 교환이 가능해 temp
와 같은 다른 변수를 선언할 필요가 없다.O(n^2)
이여서 비효율적이다.