Goal

• Bubble Sort에 대해 설명할 수 있습니다.
• Bubble Sort 과정에 대해 설명할 수 있습니다.
• Bubble Sort을 구현할 수 있다.
• Bubble Sort의 시간 복잡도와 공간 복잡도를 계산할 수 있습니다.

---

Abstract

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 입니다.

이름의 유래는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 합니다.

---

Process (Ascending)

1. 1회전에 첫 번째 원소와 두 번쨰 원소를, 두 번째 원소와 세 번째 원소를 이런 식으로 (마지막 - 1)법ㄴ째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환을 합니다.

2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다.

Python Code

def bubble_sort(arr):
	for i in range(len(arr) - 1, 0, -1):
    	for j in range(i):
        	if arr[j] > arr[j + 1]:
            	arr[i], arr[j + 1] = arr[j + 1], arr[j]

---

시간복잡도

시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + ... + 2 + 1 => n(n-1)/2 이므로, O(n^2) 입니다. 또한 bubble sort는 정렬이 돼있던 안돼있던, 2 개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일합니다.

---

공간복잡도

주어진 배열 안에서 교환 (swap)을 통해, 정렬이 수행되므로 O(n) 이다.

---

장점

• 구현이 매우 간단하고 소스코드가 직관적입니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않습니다.
• 안정 정렬(Stable Sort)입니다.

---

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로 굉장히 비효율적입니다.
• 정렬 되어있지 않은 원소가 정렬되었을 때 자리로 가기 위해서 교환 연산이 많이 일어나게 됩니다.