버블정렬(Bubble Sort)

버블정렬(Bubble Sort)도 선택정렬(Selection Sort)처럼 제일 큰 원소를 옮기는 작업을 반복하는 정렬이다. 다만, 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다.

선택정렬(Selection Sort) 이란 ? 클릭 선택정렬(Selection Sort)

버블정렬(Bubble Sort)는 위의 예제 처럼 배열의 처음 인덱스부터 n-1 인덱스까지 이동하면서 인접하는 다음 인덱스의 원소와 크기를 비교하여 순서를 바로 잡아 나간다. 이 과정을 반복하게 되면 배열의 맨끝에는 배열의 가장 큰 원소가 자리하게 된다. 그러면 배열의 제일 마지막을 잊어버리고 이를 반복하게 되면 배열이 차례대로 끝에서 부터 내림차순으로 정렬되게 된다.

버블정렬(Bubble Sort)의 슈도코드는 다음과 같다.

버블정렬(Bubble Sort)의 수행시간을 살펴보면

①의 for 루프는 n-1번 반복

②의 for 루프는 각각 n-1, n-2, ... , 2, 1번 반복

③은 상수 시간 작업

따라서, 버블정렬의 시간복잡도는 다음과 같다.

T(n) = (n-1) + (n-2) + ... + 2 + 1 = O(n^2)