지난 글 : [알고리즘/Do it 알고리즘] - 정렬 알고리즘
버블 정렬 알아보기
버블 정렬 프로그램 만들기
버블 정렬 알고리즘을 프로그램으로 구현해보자. 변수 i값을 0부터 n - 2까지 1씩 증가시키며 패스를 n - 1번 수행하는 프로그램이다.
알고리즘 개선하기 1
만약 임의로 저장된 요소가 정렬하려는(여기서는 오름차순) 방식과 유사하게 정렬되어 있다면 패스(요소값을 비교하고 위치를 변경하는 작업)를 많이 진행할 필요가 없다. 어떤 패스에서 요소의 교환 횟수가 0번이면 더 이상 정렬할 요소가 없다는 뜻이기에 정렬 작업을 멈춘다. 이런 멈춤 방식을 도입하면 정렬을 마친 배열이나 정렬이 거의 다 된 상태의 배열에 대한 비교 연산이 많이 생략되어 짧은 시간에 정렬을 마칠 수 있다. 아래는 이 '멈춤'으로 개선한 버블 정렬 메서드다.
static void bubbleSort(int[] a, int n) {
for(int i = 0; i < n - 1; i++) {
int exchg = 0;
for(int j = n - 1; j > i; j--)
if(a[j - 1] > a[j]) {
swap(a, j - 1, j);
exchg++;
}
if (exchg == 0) break;
}
}변수 exchg를 추가했다. 패스를 시작하기 직전 exchg값을 0으로 하고, 요소를 교환할 때마다 1씩 증가시킨다. 따라서 패스를 종료한(안쪽 for문의 반복이 완료) 시점에 변수 exchg값은 해당 패스의 교환 횟수다. 패스를 종료한 시점에서 exchg값이 0이라면 정렬을 완료했다 판단할 수 있으므로 break문에 의해 바깥쪽의 for문을 강제로 나와 함수를 종료한다.
알고리즘 개선하기 2
새로운 배열 {1, 3, 9, 4, 7, 8, 6}을 버블 정렬한다. 이 배열은 첫 번째 패스에서 마지막 교환을 완료하면 앞쪽의 요소 {1, 3, 4}는 정렬이 완료된 상태다. 이처럼 각 패스에서 비교, 교환을 하다 어떤 시점 이후에 교환하지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태라 생각해도 좋다. 따라서 두 번째 패스는 첫 요소를 제외한 6개 요소가 아니라 4개 요소를 비교, 교환하면 된다. 이런 내용을 바탕으로 개선한 메서드다.
static void bubbleSort(int[] a, int n) {
int k = 0;
while(k < n - 1){
int last = n - 1;
for(int j = n - 1; j > k; j--)
if(a[j - 1] > a[j]) {
swap(a, j - 1, j);
last = j;
}
k = last;
}
}last는 각 패스에서 마지막으로 교환한 두 요소 중 오른쪽 요소(a[j])의 인덱스를 저장하기 위한 변수다. 교환할 때마다 오른쪽 요소의 인덱스값을 last에 저장한다. 하나의 패스를 마쳤을 때 last값을 k에 대입해 다음에 수행할 패스의 범위를 제한한다. 그럼 다음 패스에서 마지막으로 비교할 두 요소는 a[k]와 a[k + 1]이 된다.
참고 서적 :
