버블 정렬
버블 정렬은 단순 정렬 분류에 속한다. 이해하기 쉬워서 이렇게 불리지만, 더 빠르다고 알려진 정렬 알고리즘보다 비효율적이다.
기본적인 정렬 알고리즘인 버블 정렬(bubble sort)는 다음과 같은 단계를 따른다.
배열 하나를 정렬하고 싶다고 가정하자.
배열의 처음 상태는 다음과 같다.
[ 5 , 2 , 7 , 1 , 3 ]
- 1단계 : 먼저 5와 2를 비교한다.
[ 5 , 2 , 7 , 1 , 3 ]
- 2단계 : 순서가 맞지 않으므로 둘을 교환한다.
[ 2 , 5 , 7 , 1 , 3 ]
- 3단계 : 5와 7을 비교한다.
순서가 올바르므로 교환할 필요가 없다.
[ 2 ,5 , 7 , 1 , 3 ]
- 4단계 : 7과 1을 비교한다.
[ 2 , 5 , 1 , 7 , 3 ]
- 5단계 : 순서가 맞지 않으니 교환한다.
[ 2 , 5 , 1 , 7 , 3 ]
- 6단계 : 7과 3을 비교한다.
[ 2 , 5 , 1 , 3 , 7 ]
- 7단계 : 순서가 맞지 않는다. 교환해주자.
첫 번째 정렬이 끝났다. 배열에서 가장 큰 값인 7을 가장 오른쪽으로 옮겼다. 그림이 그려지는가.
알고리즘은 큰 값을 계속해서 오른쪽으로 보내고 있다. 정렬이 완성 됐을 때 오른쪽 기준으로부터 내림차순이 될 것 같지 않은가?
아마 이 알고리즘을 버블 정렬이라 부르는 이유는 이것인 것 같다. 수면 위의 거품. 즉, 7이다.
다음 정렬도 진행해보자. 다음 거품이 무엇인지 알 수 있을 것이다.
[ 2 , 5 , 1 , 3 , 7 ]
- 8단계 : 2와 5를 비교한다
올바른 순서이므로 넘어가자.
[ 2 , 5 , 1 , 3 , 7 ]
- 9단계 : 5와 1을 비교한다.
[ 2 , 1 , 5 , 3 , 7 ]
- 10단계 : 순서가 맞지 않는다. 교환해주자.
[ 2 , 1 , 5 , 3 , 7 ]
- 11단계 : 5와 3을 비교한다.
[ 2 , 1 , 3 , 5 , 7 ]
- 12단계 : 맞지 않으니 교환해준다.
우리는 7이 올바른 위치에 있다는 것을 안다. 고로 5와 7을 비교해 줄 필요는 없다.
두 번째 정렬이 끝났다. 다음 거품인 5를 확인 했다.
세 번째 정렬을 진행해보자.
[ 2 , 1 , 3 , 5 , 7 ]
- 13단계 : 2와 1을 비교한다.
[ 1 , 2 , 3 , 5 , 7 ]
- 14단계 : 순서가 맞지 않으니 바꿔준다.
[ 1 , 2 , 3 , 5 , 7 ]
- 15단계 : 2와 3을 비교한다.
[ 1 , 2 , 3 , 5 , 7 ]
- 16단계 : 순서가 올바르니 그대로 둔다.
세 번째 정렬도 이렇게 끝이 났다. 5와 7이 올바른 위치에 있다는 것을 알고 있으니 더 이상 비교해 줄 필요는 없다.
마지막 네번 째 정렬을 해보자.
[ 1 , 2 , 3 , 5 , 7 ]
순서가 올바르다. 뒤에 값은 올바른 순서인 것을 알고 있으니 네번 째 정렬도 끝낼 수 있다.
버블 정렬 구현
다음은 자바로 구현해본 버블 정렬이다.
// 버블정렬 메소드
public static boolean bubbleSort( int[] array ) {
// 배열의 마지막 인덱스
int sortUntilIndex = array.length - 1;
// 배열의 정렬 여부
boolean sorted = false;
// 정렬 여부가 true라면 종료! 정렬될 때까지 계속 실행 된다.
while( !sorted ) {
// 조건문이 실행되지 않는다면 sorted는 true
// 이는 완전히 정렬 됐다는 뜻이다.
sorted = true;
sortUntilIndex는 정렬이 한 번씩 진행될 때마다 1씩 감소시켜준다.
for(int i = 0; i < sortUntilIndex; i++)
// 오른쪽 값보다 현재 값이 크다면 교환!
if( array[i] > array[i+1] ) {
int tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
sorted = false;
}
}
sortUntilIndex -= 1;
}
return true;
}버블 정렬의 효율성
버블 정렬은 두 가지 단계로 진행된다. 비교와 교환이다.
먼저 버블 정렬에서 비교가 얼마나 일어나는지 살펴보자.
위의 예시에서 배열의 원소는 다섯개였다. 첫 번째 정렬을 진행했을 때 차례대로 두 수의 비교를 4번 했었다.
똑같이 두 번째 정렬에서는 비교를 세번을 했었다. 첫 번째 정렬에서 가장 큰 수가 오른쪽으로 이동했으므로 마지막 두 숫자를 비교할 필요가 없었기 때문이었다.
세 번째 정렬에서는 비교를 두 번 , 네 번째에서는 한 번 했다.
이를 정리하면 4 + 3 + 2 + 1 = 10이다.
원소를 N이라고 했을 때 공식은 이렇게 나타낼 수 있다.
( N - 1 ) + ( N - 2 ) + ( N - 3 ) + ( N - 4 ) --- + 1 의 비교가 일어난다.
이제 버블 정렬에서 교환이 얼마나 일어나는지 살펴보자.
최악의 경우를 생각해보자. 아마 배열은 오름차순이 아닌 내림차순으로 정렬되어 있을 것이다.
배열에 5개의 원소가 있을 때 위의 과정대로라면,
첫 번째 정렬은 4번, 두 번째 정렬은 3번 , 세 번째 정렬은 2번, 마지막은 1번, 총 10번 해야한다.
이를 정리하면, 4 + 3 + 2 + 1 = 10이다.
그렇다면 비교와 교환을 더했을 때 총 20단계가 걸린다는 것을 알 수 있다.
만약 값 10개인 배열에서는? 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45이다.
비교 45와 교환 45이니 총 90번이 걸릴 것이다.
매우 비효율적이다. 원소 수가 많아질 수록 단계 수가 엄청나게 증가하고 있다.
다음은 표로 정리한 것이다.
| 데이터 원소 | 버블 정렬의 단계 수 | N² |
|---|---|---|
| 5 | 20 | 25 |
| 10 | 90 | 100 |
| 20 | 380 | 400 |
| 40 | 1560 | 1600 |
| 80 | 128 | 6400 |
데이터 값이 N개라면 버블 정렬에는 N²이 필요하다. 이를 빅 오로 나타내면 버블 정렬의 효율성은 O(N²)이다. 이는 매우 비효율적인 알고리즘으로 간주된다.
빅 오에 대한 내용은 빅 오 표기법 게시물에서 볼 수 있다.
포스팅 도중 느낀점..
배열과 표를 직접 쓰고 꾸미려니 시간이 여간 드는게 아니다. 이미지를 쓰고 싶다. 하지만 이미지를 아무 곳에서나 막 퍼올 수는 없는 노릇이다.
방법을 찾아봐야겠다.
