버블 정렬(Bubble sort)이란?

버블 정렬이란?

뽀글뽀글 올라는 것처럼 보인다고 해서 붙여진 이름이다.

인접한 두 항목의 값을 비교해서 일정한 기준을 만족하면 서로의 값을 교환하여 정렬하는 방식이다.

오름차순 정렬은 두 항목의 값을 비교하여 앞 쪽 값이 더 크면 두 항목의 값을 교환하고 내림차순 정렬은 두 항목의 값을 비교하여 앞쪽 값이 더 작으면 두 항목의 값을 교환하는 방식.

 

버블 정렬의 특징은?

구현이 매우 간단한 장점

선택정렬과 유사함.

 

시간복잡도는?

(n-1) + (n-2) + (n-3) + ... + 2 + 1 이므로, n(n-1)/2 으로 표기할 수 있다.

시간복잡도는 O(n²) 로 , 최선과 최악일 때가 동일하다.

버블정렬은 옆에 있는 숫자와 계속 비교를 해야하기 때문에 굉장히 비효율적이다.

 

버블 정렬의 성능 개선 방법은?

버블 정렬은 사용하는 배열의 항목 값이 완전히 뒤섞여 있는 경우도 있지만, 어느정도 순차적으로 나열되어 있는 경우가 있다.

그래서 버블정렬을 사용하여 정렬을 하다보면, 단계가 다 끝나지 않았는데 정렬이 완료되는 경우가 있다.

즉, 이미 정렬이 완료가 됐다고 하더라도 버블 정렬 특성상 중간에 중단하지 못하고 계속 진행되어야 합니다.

따라서, 비효율적입니다.

이 부분을 개선하기 위해서는

정렬 작업을 중단하도록 break; 문을 사용해서 도중에 빠져나올 수 있도록 하면 개선할 수 있다.