Bubbl Sort
서로 인접한 두 원소의 대소를 비교하여 두 원소의 자리를 교환하며 정렬하는 알고리즘이다.
탐색 과정
정렬되지 않은 배열을 예시로 들어보자.
{3, 2, 4, 5, 6, 1}
round 1
round 시작전 원본 배열 {3, 2, 4, 5, 6, 1}
-
{2,3,4,5,6,1}- 2와 3을 비교하였다. 3이 더 크기 때문에 자리를 변경해준다. -
{2,3,4,5,6,1}- 3과 4를 비교하였다. 4가 더 크기 때문에 자리는 바꾸지 않는다. -
{2,3,4,5,6,1}- 4와 5를 비교하였다. 5가 더 크기 때문에 자리는 바꾸지 않는다. -
{2,3,4,5,6,1}- 5와 6을 비교하였다. 6이 더 크기 때문에 자리는 바꾸지 않는다. -
{2,3,4,5,1,6}- 6과 1을 비교하였다. 6이 1보다 크기 때문에 서로 자리를 바꾸었다.
이렇게 제일 큰 숫자 6이 마지막에 가게 되는 것을 볼 수 있고 이 과정을 하나의 round로 본다.
round 2
round 시작전 원본 배열 {2,3,4,5,1,6}
-
{2,3,4,5,1,6}- 2와 3을 비교하였다. 3이 더 크기 때문에 자리를 변경하지 않는다. -
{2,3,4,5,1,6}- 3과 4를 비교하였다. 4가 더 크기 때문에 자리를 변경하지 않는다. -
{2,3,4,5,1,6}- 4와 5를 비교하였다. 5가 더 크기 때문에 자리를 변경하지 않는다. -
{2,3,4,1,5,6}- 5와 1을 비교하였다. 5가 더 크기 때문에 자리를 변경해준다.
round 1에서 6은 마지막 위치에 정렬 완료되었기에 탐색하지 않는다.
round 3
round 시작전 원본 배열 {2,3,4,1,5,6}
-
{2,3,4,1,5,6}- 2와 3을 비교하였다. 3이 더 크기 때문에 자리를 변경하지 않는다. -
{2,3,4,1,5,6}- 3과 4를 비교하였다. 4가 더 크기 때문에 자리를 변경하지 않는다. -
{2,3,1,4,5,6}- 4과 1을 비교하였다. 4가 더 크기 때문에 자리를 변경해준다.
round 2에서 5는 정렬 완료가 되었으므로 탐색하지 않는다.
round 4
round 시작전 원본 배열 {2,3,1,4,5,6}
-
{2,3,1,4,5,6}- 2와 3을 비교하였다. 3이 더 크기 때문에 자리를 변경하지 않는다. -
{2,1,3,4,5,6}- 3과 1을 비교하였다. 3이 더 크기 때문에 자리를 변경해준다.
round 3에서 4는 정렬이 완료되었으므로 탐색하지 않는다.
round 5
round 시작전 원본 배열 {2,1,3,4,5,6}
{1,2,3,4,5,6}- 2와 1을 비교하였다. 2가 더 크기 때문에 자리를 변경해준다.
round 4에서 3은 정렬이 완료되었으므로 탐색하지 않는다.
위의 과정을 보면 라운드 별로 탐색시 각 라운드에서 가장 큰 값이 오른쪽으로 이동하게 된다. 이러한 과정을 거치면 거품 정렬을 이용하여 정렬이 완성되게 된다. 위의 과정을 통해 도출해낸 정보를 아래에 정리해 본다.
round는
배열의 원소의 개수 - 1만큼 진행되고 round 별 탐색 횟수는배열의 원소의 개수 - 해당 round의 수만큼 탐색한다.
코드는 아래와 같다.
코드
첫번째 반복문은 round이고 두번째 반복문은 round 당 탐색 횟수를 나타낸다.
만약에 j = 0이라면 arr[0] 과 arr[1]를 비교하는 조건 식이 들어가 있다.
Bubble Sort의 특징
-
데이터를 비교하면서 찾기 때문에 비교 정렬이라고 한다.
-
배열이외에 추가적인 공간을 필요로 하지 않기 때문에 제자리 정렬(in-place-sort)이라고 한다.
엄밀히 말하자면 temp의 임시 데이터가 존재하지만 무시할 수준의 변수이기에 제자리 정렬로 취급한다. -
앞에서 부터 차례대로 비교하기 때문에 안전 정렬이라고 한다.
장점
-
제자리 정렬의 특징으로 추가적인 메모리 소비가 적다.
-
코드가 직관적이기에 구현하기 쉽다.
-
안정 정렬이 가능하다.
단점
- 시간복잡도가 최악, 평균 모두 O(n^2)로, 굉장히 비효율적이다.
시간복잡도
i=1일 때, 데이터 비교 회수는 N-1번
i=2일 때, 데이터 비교 회수는 N-2번
i=3일 때, 데이터 비교 회수는 N-3번
.
.
.
i=N-1일 때, 데이터 비교 회수는 1번
즉, (N-1)(N-2)(N-3)...3+2+1 = N(N-1)/2
O(N^2)가 된다.
참고
https://st-lab.tistory.com/195
https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html
