버블 정렬 알고리즘(Bubble Sort Algorithm)

 버블 정렬 알고리즘은 대표적인 쉬운 정렬 알고리즘이지만 성능 면에서 좋은 모습을 보여주지는 못합니다.

 버블 정렬 알고리즘의 이름은 정렬하는 모양이 버블과 비슷하다고 해서 붙여진 이름입니다. 구조를 살펴보면 순차적으로 바로 옆에 있는 데이터와 비교해서 옆의 데이터가 크면 자신과 위치를 바꾸면서 가장 큰 값을 수면에 방울이 올라오듯이 나타난다고 해서 버블 정렬입니다.

 다음은 버블 정렬을 구현한 소스코드입니다.

*나머지 코드는 이전 글과 동일합니다.

결과 또한 전과 똑같기에 생략합니다.

 버블 알고리즘의 성능 역시 시간복잡도로 표기하면 O(N^2)입니다. 다른 정렬 알고리즘과 성능이 같아 보이지만 버블 정렬 알고리즘의 성능은 최선의 경우와 최악의 경우 각각에 따라 달라집니다. 버블 알고리즘의 비교 횟수는 N * N / 2회이며 최선의 경우일 때 이동 횟수는 0, 최악의 경우일 때는 N * N / 2회입니다. 이로 보건대, 버블 정렬 알고리즘은 최악의 경우를 가정했을 때 알고리즘 성능이 다른 정렬 알고리즘보다 많이 나쁩니다. 이유는 비교와 복사를 반복 실행하기 때문입니다.