[Algorithm] 버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

 

버블 정렬은, 이웃한 두 숫자를 계속해서 비교하며 정해진 규칙에 따라 자리를 스위칭하는 정렬이다. 예를 들어, 오름차순이라면 이웃한 두 숫자 중 더 큰 숫자가 뒷 자리로 이동하도록 서로 바꿔준다는 것이다. 버블 정렬이라는 이름이 붙은 이유는 가장 가벼운 것이 위로 올라가는 거품의 움직임에 빗대어 붙여진 이름이라 한다. (그렇게 공감이 가진 않는다)

 

버블 소트 (출처 : https://wonjayk.tistory.com/)

 

위 그림은 버블 정렬의 switching 하는 과정을 보여주는 그림이다.

연속된 두 이웃의 값을 비교해 더 높은 값을 뒷자리로 스위칭하게 된다.

특징은, 한 loop가 돌 때마다, 제일 마지막 자리의 숫자가 결정된다는 것이다.

다음 loop는 n-1번째 자리의 숫자가, 그 다음은 n-2번째 자리의 숫자가 결정된다는 특징을 알게 된다면, 쉽게 구현할 수 있다.

 

모든 자리의 숫자를 결정해야 하고 (O(n)), n번째 자리의 숫자를 결정할 때 마다 n-1번의 비교가 이뤄진다. (O(n))

따라서 버블 정렬의 시간 복잡도는 O(n^2)에 해당한다.

 

 

버블 정렬 파이썬 코드

 

버블 정렬 자바 코드

 

 

버블 정렬 장단점

- 버블 정렬의 장점

구현이 간단하므로, 개발에 드는 시간을 줄일 수 있다.

코드만 보고도 누구나 이해하기 쉬운 직관적인 코드이다. 

공간 복잡도가 O(N)으로, 메모리를 아낄 수 있다.

 

- 버블 정렬의 단점

데이터를 하나씩 비교하기 때문에 비교횟수가 많아지므로, 시간이 오래 걸린다.