버블 정렬 (Bubble sort)
이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 방법
패스(pass) : 이웃한 두 요소를 처음부터 끝까지 비교, 교환한 한번의 사이클
첫번째 패스에서는 n - 1회이고, 두번째 횟수는 n - 2회다.
맨 처음부터 끝까지 오름차순
static void bubbleSort(){
int i, j, temp;
int[] array = {1, 4, 6, 9, 10, 2, 5, 8, 7, 3};
for(i = 0; i < array.length; i++) {
for(j = 0; j < array.length - 1 - i; j++) {
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}맨 끝부터 처음으로 오름차순
static void bubbleSort(){
int i, j;
int[] array = {1, 4, 6, 9, 10, 2, 5, 8, 7, 3};
for(i = 0; i < array.length - 1; i++)
for(j = array.length - 1; j > i; j--)
if(array[j - 1] > array[j])
swap(array, j - 1, j);
}
static void swap(int[] array, int j1, int j2){
int temp = array[j1];
array[j1] = j2;
array[j2] = temp;
}비교 횟수는 첫번째 패스가 n - 1, 두번째 패스가 n - 2 ... 이므로 그 합계는 (n - 1) + (n - 2) + ... + 1 = n(n-1)/2 가 된다.
하지만 실제 요소를 교환하는 횟수는 배열의 요솟값에 더 많이 영향을 받기 때문에 교환 횟수의 평균값은 비교 횟수의 절반인 n(n - 1)/4 회이다.
또한 swap 메서드 안에서 값의 이동이 3회 발생하므로 이동 횟수의 평균은
3n(n - 1)/4 회가 된다.
💡 [업그레이드 1] 맨 끝부터 처음으로 오름차순
만약 n번째 패스에서 이미 정렬을 다 끝냈다고 한다면 그 패스에서는 요소의 교환이 한 번도 이루어지지 않았을 것이다.
즉, 어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻이기에 정렬 작업을 멈추면 된다.
static void bubbleSort(){
int i, j;
int[] array = {1, 4, 6, 9, 10, 2, 5, 8, 7, 3};
for(i = 0; i < array.length - 1; i++)
int exchag = 0; // 패스의 교환 횟수
for(j = array.length - 1; j > i; j--)
if(array[j - 1] > array[j]){
swap(array, j - 1, j);
exchag++;
}
if (exchag == 0) break; // 교환 횟수가 0이면 종료
}💡 [업그레이드 2] 맨 끝부터 처음으로 오름차순
예를 들어 {1, 3, 9, 7}의 배열을 오름차순으로 정렬할 때, 앞의 1, 3은 이미 잘 정렬되어 있다. 그럼 9와 7이 교환을 끝내면 더 이상 정렬을 하지 않아도 된다.
이렇게 각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태라고 생각할 수 있다.
static void bubbleSort(){
int[] array = {1, 4, 6, 9, 10, 2, 5, 8, 7, 3};
int k = 0; // array[k]보다 앞쪽은 정렬을 마친 상태
while(k < array.length - 1){
int last = array.length - 1; // 마지막으로 요소를 교환한 위치
for(int j = array.length - 1; j > k; j--)
if(array[j - 1] > array[j]){
swap(array, j - 1, j);
last = j;
}
k = last;
}
}last는 각 패스에서 마지막으로 교환한 두 요소 가운데 오른쪽 요소(array[j])의 인덱스를 저장하기 위한 변수이다.
교환을 수행할 때마다 오른쪽 요소의 인덱스 값을 last에 저장한다.
하나의 패스를 마쳤을 때 last 값을 k에 대입하여 다음에 수행할 패스의 범위를 제한한다.
메서드 시작 부분에 k를 0으로 초기화한 이유는 첫 번째 패스에서는 모든 요소를 검사해야 하기 때문이다.
양방향 버블 정렬 (bidirection bubble sort)
{9,1,3,4,6,7,8} 배열에서는 업그레이드 2의 알고리즘을 사용해도 빠른 시간 안에 정렬 작업을 마칠 수 없다. 왜냐하면 맨 앞에 있는 요소의 값(9)는 1회의 패스를 거쳐도 한 칸씩만 뒤로 가기 옮겨지기 때문이다.
그래서 홀수 번째의 패스는 가장 작은 요소를 맨 앞으로 옮기고,
짝수 번째의 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식을 사용하면(패스의 스캔 방향을 교대로 바꾸면) 비교 횟수를 줄일 수 있다.
이 방법은 칵테일 정렬(cocktail sort) 또는 셰이커 정렬(shaker sort)이라는 이름으로도 불린다.
static void shakerSort(){
int[] array = {9,1,3,4,6,7,8};
int left = 0;
int right = array.length - 1;
int last = right;
while(left < right){
for(int j = right; j > left; j--){
if(array[j - 1] > array[j]){
swap(array, j - 1, j);
last = j;
}
}
left = last;
for (int j = left; j < right; j++){
if (array[j] > array[j + 1]){
swap(array, j, j + 1);
last = j;
}
}
right = last;
}
}