6-2. 버블 정렬(Bubble sort)

버블 정렬

: 버블 정렬은 이웃한 두 요소의 대소 관계를 비교해 교환을 반복한다.

 

 

 

먼저 끝에 있는 두 요소 9와 8부터 시작

오름차순으로 배열을 정렬하고자 한다면 왼쪽의 값 < 오른쪽의 값 -> 9와 8 교환

 

 

 

뒤이어 2, 3번째 요소(1, 8) 비교

1은 8보다 작으므로 교환X

 

 

 

같은 작업을 첫 번째 요소까지 계속한 결과

 

이러한 일련의 과정(비교, 교환 작업)을 패스(pass)라고 하고, 요소의 개수가 n개인 배열에서는 패스를 n - 1회 수행한다.

이어 배열의 2번째 이후 요소에 대한 비교, 교환을 하는 패스를 수행하며, 첫 번째 패스보다 1회 적은 n - 2회의 패스를 수행하게 된다.

 

 

 

 

 

버블 정렬 프로그램

 

• 버블 정렬 알고리즘을 프로그램으로 구현
• 변수 i의 값을 0부터 n - 2까지 1씩 증가하며 n - 1회의 패스를 수행

 

 

for(int i = 0; i < n - 1; i++) {
	//a[i], a[i + 1], ..., a[n - 1]에 대해
    //끝에서부터 앞쪽으로 스캔하면서 이웃하는 두 요소를 비교해 교환
}

 

 

총 비교 횟수

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2 (회)

 

 

 

[실습 코드]

//a[idx1]와 a[idx2]의 값을 바꾼다.
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    //버블 정렬
    static void bubbleSort(int[] a, int n) {
        for(int i = 0; i < n - 1; i++) {
            for(int j = n - 1; j > i; j--) {
                if(a[j] < a[j - 1])
                    swap(a, j, j - 1);
            }
        }
    }

 

 

 

 

 

알고리즘 개선(1)

 

이미 배열이 정렬을 마친 상태라면 그 이후의 패스는 요소 교환X

• 즉, 어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻이므로 정렬 작업 중지

 

 

[실습 코드]

static void bubbleSort2(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;
            }

 

 

 

 

 

알고리즘 개선(2)

 

• 각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태

 

 

[실습 코드]

static void bubbleSort3(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] < a[j - 1]) {
                    swap(a, j, j - 1);
                    last = j;
                }
                k = last;
            }