버블 정렬의 동작 과정 이해하기

버블 정렬은 빠른 알고리즘은 아니지만 비교와 교환만으로 정렬이 만들어지는 과정을 가장 직접적으로 보여준다. 한 번의 순회가 배열의 끝에 어떤 값을 남기는지부터 살펴봤다.

Bubble Sort(버블 정렬)

두 인접한 원소를 비교하고 필요한 경우 위치를 교환함으로써 정렬을 수행한다. 간단한 알고리즘이지만 최악, 평균, 최선의 경우 시간 복잡도는 모두 O(n^2)로 비효율적이다.

동작 방식

1. 첫 번째 자료와 두 번째 자료를 비교한다.
2. 정렬 조건에 맞지 않다면 두 자료의 위치를 바꾼다.
3. 정렬 조건에 맞다면 다음 자료들을 비교한다.
4. 마지막 자료까지 반복한다.
5. 정렬된 자료를 제외하고 첫 번째 자료부터 모든 과정을 계속해서 반복한다.