거품 정렬(Bubble Sort) 이란?
두 개의 인접한 원소를 비교하여 정렬하는 방식.
👉 거품 정렬은 데이터를 비교하면서 찾기 때문에 '비교 정렬'이다.
👉정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요올 하지 않기 때문에 '제자리 정렬(in-place sort)' 이기도 하다.
선택 정렬과 같이 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 무시 가능한 적은 양이기 때문에 제자리 정렬로 본다.
선택 정렬과는 달리 거품 정렬은 앞에서부터 차례대로 비교하기 때문에 '안정 정렬'이기도 하다.
평균 시간 복잡도는 O(N^2) 이다.
거품 정렬(Bubble Sort) 방법
(오름차순 기준)
1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.
2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.
3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다.
각 라운드를 진행 할 때마다 맨 뒤에서 부터 한 개씩 정렬되기 때문에, 라운드 진행 될 때마다 한 번씩 줄면서 비교하게 된다.
총 라운드 횟수 : 배열 크기 -1
각 라운드 별 비교 횟수 : 배열 크기 - 라운드 횟수
✏ 추가로, 각 라운드에서 비교수행을 할 때에 원소 교환(swap)이 일어나지 않았다면, 이미 정렬된 데이터라는 의미이다.
이 상황에서의 정렬 종료 조건문을 넣어주면 최선의 시간 복잡도 O(N)을 만들어줄 수 있다.
거품 정렬(Bubble Sort)의 장단점
👍 추가적인 메모리 소비가 작다.
👍 구현이 매우 쉽다.
👍 안정정렬이 가능하다.
👎 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.
Reference
매일매일 성장하는 개발자