Bubble Sort(거품 정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Bubble Sort(거품 정렬)

거품 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 로 상당히 느리지만,

코드가 단순하기 때문에 자주 사용된다.

출처 : 위키 백과

예제

[4, 54, 2, 8, 63, 7, 55, 56]        [4, 2, 8, 54, 7, 55, 56, 63]        [2, 4, 8, 7, 54, 55, 56, 63]

[4, 2, 54, 8, 63, 7, 55, 56]        [2, 4, 8, 54, 7, 55, 56, 63]        [2, 4, 7, 8, 54, 55, 56, 63]

pass3

[4, 2, 8, 54, 63, 7, 55, 56]        [2, 4, 8, 7, 54, 55, 56, 63]

pass 2

[4, 2, 8, 54, 7, 63, 55, 56]

[4, 2, 8, 54, 7, 55, 63, 56]

[4, 2, 8, 54, 7, 55, 56, 63]

pass1

의사 코드

Bubble Sort(A[], n) {    // 배열 A[1...n]을 정렬
for last <- n down to 2 {    -------------------------- ①
for i <- 1 to last-1    --------------------------- ②
if(A[i] > A[i+1]) then A[i] <-> A[i+1];    ---- ③
}
}

실행 시간 : (n-1) + (n-2) + ... + 2 + 1 = Θ(n²)

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

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

③ 의 교환은 상수시간 작업

시간복잡도

T(n) = (n-1) + (n-2) + ... + 2 + 1 = Θ(n²)

소스코드(Java)