버블 정렬 (Bubble Sort)

-서로 이웃한 데이터들을 비교하며

가장 큰 데이터를 맨 뒤로 보내며 정렬하는 방식-

최악의 경우 시간복잡도는 O(n^2),

최선의 경우 시간복잡도는 O(n),

평균 시간복잡도는 O(n^2)이다.

(시간 복잡도의 개념을 알고 싶다면 위키보다는 이 블로그를 추천한다.)

평균이 O(n^2)인 느린 알고리즘이지만, 병렬 처리에 적합하며 코드가 간단하다.

왜 느리냐 하면은, 모든 요소에 대해 비교하고, 해당 되는 요소에 교환을 하기 때문.

데이터들을 교환 시킬 때 거품이 수면 위로 올라오는 것 같다 하여

버블 정렬이라고 한다.

(실제로 버블정렬 애니메이션을 보면 그렇게 보이는 것 같다)

-Sample Source-

Binary Weaver