랜덤한 수를 정렬하는 여러가지의 정렬법중에 버블 정렬에 대해서 알아보고 해당 알고리즘이 가지는 특징 과 장단점에 대해서 알아보도록 하자
버블 정렬(Bubble sort)의 특징
버블정렬의 특징으로는 가장 큰 숫자를 맨 오른쪽으로 보내 계속 채운다는 것이다
{7, 2, 9, 1, 3}
아래와 같은 배열이있을때 버블정렬을 하게되면 아래와같은 표로 정렬되게된다
| 첫번째정렬 | 2 | 7 | 1 | 3 | 9 |
| 두번째정렬 | 2 | 1 | 3 | 7 | 9 |
| 세번째정렬 | 1 | 2 | 3 | 7 | 9 |
| 네번째정렬 | 1 | 2 | 3 | 7 | 9 |
위에 표처럼 첫번째 정렬시도를 할때 가장큰숫자가 맨오른쪽부터 차곡차곡 쌓이는 형태를 볼수있다
본격적으로 코드를 보면서 버블정렬을 어떤식으로 구현하는지 알아보도록 하자
int[] bubbleSort = {7, 2, 9, 1, 3};
가장처음 정수형 배열을 선언해주고 안에 값은 할당해준다
int[] bubbleSort = {7, 2, 9, 1, 3};
for (int i=0; i< bubbleSort.length-1; i++) {
}그다음 반복문을 통해 배열안에 들어있는 자리수를 하나씩 줄일것이다
이게 무슨의미인가 다시보도록 하자
| 첫번째정렬 | 2 | 7 | 1 | 3 | 9 |
| 두번째정렬 | 2 | 1 | 3 | 7 | 9 |
| 세번째정렬 | 1 | 2 | 3 | 7 | 9 |
| 네번째정렬 | 1 | 2 | 3 | 7 | 9 |
위에서 말한 맨오른쪽 부터 가장 큰 숫자가 적재된다고 말했었는데 이는 두번째 시도부터는 굳이 끝까지 탐색할필요가없다
왜냐면 이미 가장큰값이 맨오른쪽에 있기때문이다
int[] bubbleSort = {7, 2, 9, 1, 3};
for (int i=0; i< bubbleSort.length-1; i++) {
for (int j=0; j< bubbleSort.length-1-i; j++) {
}
}
가장 바깥쪽 반복문에서는 0, 1, 2, 3, 4 씩 증가되며 해당값을 j에서 빼도록한다 그러면 아래 표와같이 반복하게될것이다
| i | j | 설명 | 결과 | ||
| 0 | 4 | 3번째 index까지 탐색하며 비교(0,1,2,3,4) | {2,7,1,3,9} | ||
| 1 | 3 | 2번째 index까지 탐색하며 비교(0,1,2,3,4) | {2,1,3,7,9) | ||
| 2 | 2 | 1번째 index까지 탐색하며 비교(0,1,2,3,4) | {1,2,3,7,9) | ||
| 3 | 1 | 0번째 index까지 탐색하며 비교(0,1,2,3,4) | {1,2,3,7,9} | ||
이런식으로 바로앞에 수와 비교했을때 앞에숫자가 더작다면 서로 위치를 바꿔 가장큰수가 맨오른쪽에 오게되는것이다
그리고 맨오른쪽에 있는 숫자는 이미 정렬이 끝났으므로 i만큼 j에서 뺄셈하여 다음큰수가 위치하도록한다
int[] bubbleSort = {7, 2, 9, 1, 3};
int temp;
for (int i=0; i< bubbleSort.length-1; i++) {
for (int j=0; j< bubbleSort.length-1-i; j++) {
if (bubbleSort[j] > bubbleSort[j+1]) { // 바로앞의 인덱스와비교
temp = bubbleSort[j];
bubbleSort[j] = bubbleSort[j+1];
bubbleSort[j+1] = temp;
}
}
}
바로앞의 숫자와 비교해서 앞에숫자가 작을경우 자리위치를 바꾸게되고 계속해서 큰수는 맨오른쪽으로 밀려나게된다
해당 알고리즘이 버블정렬이라고 볼수있다
버블 정렬(Bubble sort)의 장단점
그렇다면 해당 알고리즘의 장점과 단점은 무엇일까
우선 장점은 구현이 정말 단순하다는 것이다 그냥 앞에숫자와 비교해서 위치를 바꾸면 되기때문에 간단하다
단점은 우선 다시 표를한번 보도록하자
| 첫번째정렬 | 2 | 7 | 1 | 3 | 9 |
| 두번째정렬 | 2 | 1 | 3 | 7 | 9 |
| 세번째정렬 | 1 | 2 | 3 | 7 | 9 |
| 네번째정렬 | 1 | 2 | 3 | 7 | 9 |
보면 세번째 정렬부터 모든 값들이 정렬이 완료되었지만 계속해서 정렬을 수행하게된다
이는 필요없는 복잡도를 만들며 비효율적인 작업이라는 것을 알수있다
또한 가장큰값이 왼쪽에서 오른쪽으로 이동하기 위해서는 배열에있는 모든요소들과 교환이 일어나야 하는데 이경우 위에 예시처럼 이미 정렬이 되어있는 경우에도 교환이 되는일이 자주일어난다
버블정렬의 시간의복잡도는 n^2이며, 정렬에 사용되는 모든 알고리즘 통틀어서 가장 안좋은 효율을 가진다
또한 구현이 단순하지만 시간이 오래걸리기때문에 거의 사용되지않는다