버블 정렬(Bubble Sort)아 넌 누구니?

안녕하세요~ 

 

주말 하루 종일 집보러 다닌다고 엄청 걸었네요. 요즘 집값이 왜이리 비싼지 도대체 집을 살 수가 없어요 ㅜㅜ

 

언제쯤 이 집 값 버블이 좀 가라 앉을까요? 

 

이 집 값 버블처럼 버블 정렬의 시간 복잡도 역시 Ο(n²) 로 최악입니다.

 

왜 이렇게 높을까요? 버블 정렬은 도대체 어떤 알고리즘 이길래 서울 집 값처럼 높은 시간 복잡도를 갖고 있는 걸까요??
간단히 설명하자면 버블 정렬은 순차적으로 두개의 값을 비교하면서 정렬을 하는데, 정렬할 것이 없을때 까지 무한 반복하면서 정렬을 하게됩니다. 
그림을 보면서 이해해 볼까요?
자, 다음과 같은 데이터 셋이 있다고 가정해 봅시다. 다섯 개의 숫자들이 정렬되지 않은 채로 들어있음을 확인 하실 수 있을겁니다.

 

이제 이 숫자들을 버블 정렬을 이용해서 작은 숫자부터 큰 숫자 순으로 정렬을 해보도록 하겠습니다.

 

우선 가장 좌측의 두개의 숫자를 선택합니다. 14와 33이 선택이 되겠죠.

14와 33을 비교하면 왼쪽의 14가 오른쪽의 33보다 작습니다. 따라서 이 두 개의 숫자는 이미 정렬이 되어있으니 다음으로 넘어갑니다.

 

 

이번엔 두번째 인덱스에 위치한 33과 그 다음 요소인 27을 비교 합니다. 

 

 

비교를 해보니 27이 작은데 더 오른쪽에 있습니다. 

 

따라서 두 숫자의 위치를 바꿉니다.

 

그 다음에는 세번 째 인덱스의 33과 네번째 인덱스의 35를 비교합니다.

이미 정렬이 되어있는 상태이니까 순서 변경없이 다음 단계로 넘어갑니다.

 

이제 35와 10을 비교를 하겠군요. 

 

35와 10은 순서가 뒤바뀌어 있으니 위치를 바꿔줍니다.

 

여기까지 오면 ( 마지막 요소까지 검사가 끝나면 ) 가장 높은 숫자가 가장 우측에 위치하게 됩니다.

 

이 작업을 다시 한번 반복합니다. 

 

그리고 또 반복합니다.

 

마지막으로 또 반복합니다. 

 

이제 모든 숫자가 정렬이 되었음을 확인할 수 있습니다.

 

자, 버블 정렬을 할 때 input으로 총 n개의 요소가 들어왔다고 가정하면, 

 

최악의 경우 버블 정렬로 모든 숫자가 정렬이 되려면 총 (n-1) + (n-2) + .... + 3 + 2 + 1번의 작업이 필요합니다.

 

(n-1) + (n-2) + .... + 3 + 2 + 1 =  (n  *  (n - 1 ) )/ 2  = n ( n - 1 ) / 2 이므로  Ο(n²) 의 시간복잡도를 보이게 됩니다.

이해가 되시죠? 
혹 질문이 있으신 분들은 댓글 남겨주시고, 좋은 밤 되세요~~~
다음에는 삽입 정렬 알고리즘을 포스팅 하도록 하겠습니다.