버블 정렬, 그림으로 쉽게 이해하기

1. 원리

0. 사전 세팅: 정렬되지 않은 1차원 배열이 주어졌고, 해당 배열을 오름차순으로 정렬함을 전제로 한다.
1. 배열의 첫 원소를 조회한다.
2. 다음 원소와 대소관계를 비교하고, 그에 따라 적절한 조치를 한다.
   • 조회중인 원소 > 다음 원소: 둘의 자리를 바꾼다.
   • 조회 중인 원소 < 다음 원소: 아무 조치 없이 지나간다.
3. 2번 과정을 배열 끝까지 반복한다. 이러면 정렬되지 않은 영역 최우단에 정렬되지 않은 값 중 최대값이 위치하게 된다.
   (즉 3번 과정 1번 당 하나의 원소가 정렬된다.)
4. 3번 과정을 배열 내의 모든 원소가 정렬될 때까지 반복한다.

2. 예시

위 사진과 같이 주어졌을 때,

5가 1보다 큼으로 둘의 자리를 바꾼다.

5가 3보다 큼으로 둘이 자리를 바꾼다.

5는 7보다 작음으로 자리를 바꾸지 않는다.

7이 2보다 큼으로 자리를 바꾼다.

7은 9보다 작음으로 둘의 자리를 교체하지 않는다.

정렬을 한 번 진행 했더니 7이 제 위치를 찾았다. 이를 반복하면 된다.

3. 시간 복잡도

최악의 경우는 N개의 원소를 가진 배열을 오름차순으로 정렬하려 하는데, 입력은 내림차순으로 들어왔을 때이다. 이때 과정 (2) 한 번 당 하나의 원소가 정렬된다. 따라서 과정 (2)를 N번 반복해야 한다. 과정 2번 또한 N번의 조회가 필요함으로 최악의 시간 복잡도는

O ($N^{2}$)이 든다.