물 속에서 거품이 올라오는 모습과 비슷하게 정렬한다고 해서 붙여진 이름.
왼쪽 끝에서부터 인접하는 두 개의 값을 비교하여 교환하는 방식으로 오른쪽 끝까지 가는 방식.
구현은 쉽지만 상당히 비효율적인 정렬 방식으로 꼽히고 있다.
원본 리스트
|
3 |
8 |
0 |
1 |
4 |
[STEP 1]
|
3 |
8 |
0 |
1 |
4 |
- 3과 8을 비교. 8이 더 크므로 변화가 없어도 된다.
|
3 |
8 |
0 |
1 |
4 |
- 그 다음 8과 0을 비교. 0이 더 작으므로 8과 0을 교환한다.
|
3 |
0 |
8 |
1 |
4 |
- 8과 1을 비교. 1이 더 작으므로 8과 1을 교환한다.
|
3 |
0 |
1 |
8 |
4 |
- 8과 4를 비교. 4가 더 작으므로 8과 4를 교환한다.
|
3 |
0 |
1 |
4 |
8 |
- 이로써 한 스텝이 끝났다. 다시 처음부터 비교를 한다.
[STEP 2]
|
3 |
0 |
1 |
4 |
8 |
- 3과 0을 비교. 0이 더 작으므로 3과 0을 교환한다.
|
0 |
3 |
1 |
4 |
8 |
- 3과 1을 비교. 1이 더 작으므로 3과 1을 교환한다.
|
0 |
1 |
3 |
4 |
8 |
- 3과 4를 비교. 4가 더 크므로 그대로 둔다.
|
0 |
1 |
3 |
4 |
8 |
- 두번째 스텝이 끝났으며, 이런 식으로 뒤에서부터 모든 수가 채워졌을 때 스텝을 종료한다.
코드는 아래와 같다.
버블 정렬의 단점은 정렬이 된 상태에서도 마지막까지 비교하기 때문에 중간에 noChange라는 flag를 두어
변화가 없을 시에는 루프를 돌지 않도록 방어 코드를 추가했다.
