버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 중 하나로, 가장 간단하고 직관적인 알고리즘 중 하나입니다. 높은 수의 복잡도 때문에 현업에서는 잘 사용하지 않으며 학습을 위한 알고리즘입니다.

동작 방식

1. 첫 번째 원소부터 인접한 두 원소를 비교합니다.
2. 만약 왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 서로 교환합니다.
3. 오른쪽으로 한 칸씩 이동하여 다시 비교합니다.
4. 마지막 원소까지 위의 과정을 반복합니다.
5. 마지막 원소까지 정렬을 마치면 마지막 원소를 제외하고 위의 과정을 반복합니다.
6. 위의 과정을 n-1번 반복하면 모든 원소가 정렬됩니다.

시간 복잡도

• 최선의 경우: 원소들이 이미 정렬되어 있는 경우를 말합니다. 이 경우에는 원소를 비교할 필요가 없으므로, $O(n)$의 시간 복잡도를 갖습니다.
• 최악의 경우: 원소들이 역순으로 정렬되어 있는 경우를 말합니다. 이 경우에는 원소를 비교하고 교환해야 하므로, $O(n^2)$의 시간 복잡도를 갖습니다.
• 평균적인 경우: $O(n^2)$의 시간 복잡도를 갖습니다.