버블 정렬(Bubble Sort)

물 속에서 거품이 올라오는 모습과 비슷하게 정렬한다고 해서 붙여진 이름.

왼쪽 끝에서부터 인접하는 두 개의 값을 비교하여 교환하는 방식으로 오른쪽 끝까지 가는 방식.

구현은 쉽지만 상당히 비효율적인 정렬 방식으로 꼽히고 있다.

원본 리스트

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를 두어 

변화가 없을 시에는 루프를 돌지 않도록 방어 코드를 추가했다.