버블 정렬 알고리즘이란?

오늘은 정렬 알고리즘 중 가장 기본적이면서 초보자도 쉽게 이해할 수 있는 버블 정렬에 대해 소개하려고 한다

참고로 버블 정렬은 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 정렬이라고 불린다

버블 정렬이란?

버블 정렬은 인접한 두 원소를 비교하여 잘못된 순서로 되어 있다면 서로 교환하는 방식의 정렬으로

이 과정을 전체 리스트에 대해 반복하면 가장 큰 원소(또는 가장 작은 원소)가 배열의 끝으로 이동하게 되는데 그 이후에는 다시 처음부터 비교하되 마지막 원소를 제외하고 동일한 과정을 반복하는 방식으로 전체 원소를 정렬하는 방식을 가진다

버블 정렬의 작동 방식

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 오름차순으로 버블 정렬 알고리즘을 사용한다고 했을 때

정렬해야 하는 리스트: [5, 3, 8, 4, 2]

첫 번째 진행:

5와 3 비교 → 교환 → [3, 5, 8, 4, 2]
5와 8 비교 → 그대로
8과 4 비교 → 교환 → [3, 5, 4, 8, 2]
8과 2 비교 → 교환 → [3, 5, 4, 2, 8]

두 번째 진행:

3과 5 비교 → 그대로
5와 4 비교 → 교환 → [3, 4, 5, 2, 8]
5와 2 비교 → 교환 → [3, 4, 2, 5, 8]

세 번째 진행:

3과 4 비교 → 그대로
4와 2 비교 → 교환 → [3, 2, 4, 5, 8]
...

이 과정을 반복하면 리스트에 전체 원소가 오름차순으로 정렬된다

버블 정렬의 장단점

마지막으로 버블 정렬 알고리즘에 장단점을 알아보자

장점:

1. 구현이 간단하다
2. 작은 데이터셋에는 효율적일 수 있다

단점:

1. 시간 복잡도가 O(n^2)로 큰 데이터셋에는 비효율적이다
2. 실무에서 사용하기에는 다른 정렬 알고리즘에 비해 느리다