버블 정렬

버블 정렬은 배열에서 차례대로 두 개의 붙어있는 인덱스를 비교하여 더 큰 값을 뒤로 보내는 정렬 방법이다.
가장 큰 값이 먼저 맨 뒤로 보내지고 그 다음 뒤에서부터 순차적으로 정렬이 완성된다.

n = array length
처음엔 인덱스 0부터 n-2까지 그다음 인덱스와 비교하면서 다음 인덱스가 크면 서로 교환
위 절차를 0~n-3, 0~n-4, 0~n-5, ... 0~0으로 총 n-1번 순회
i : 0~n-2
j : 0~n-2-i

 

최선의 경우, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 성능이 좋지 못하여 구현이 쉽다는 장점 말고는 다른 정렬 방법과 비교했을 때 좋은 정렬 방법이 아님.