[알고리즘] 정렬2: bubble sort

Bubble

복잡도: O(n^2)
이중 루프를 돌면서 두 개씩 쌍으로(옆에 있는 것끼리) 비교하여 순서를 맞춘다. (swap) 오른쪽으로 한 칸씩 이동하면서 반복한다.
위 작업을 마치면 마지막에는 가장 큰 값이 들어가게 된다.
다시 전 작업을 반복하는데, 끝 지점을 한 칸 왼쪽으로 이동시킨다. (가장 큰 값은 찾았으므로)

-> 루프0
index 0, 1 비교. (swap)
index 1, 2 비교.
...
index n-2, n-1(마지막인덱스) 비교.
결과 ; n-1인덱스에 가장 큰 값! ; 전체 n-1 번 비교

-> 루프1
index 0, 1 비교.
index 1, 2 비교.
...
index n-3, n-2비교. (마지막 인덱스를 1씩 감소)
결국 n-2에 다음으로 큰 값! ; 전체 n-2번 비교.
...

ex)
loop i=0. j=1-4
5 1 9 3 4 : 인덱스 0, 1을 비교하여 정렬 (before) swap
1 5 9 3 4 : 인덱스 1, 2를 비교하여 정렬
1 5 9 3 4 : 인덱스 2, 3를 비교하여 정렬 swap
1 5 3 9 4 : 인덱스 3, 4를 비교하여 정렬 swap
1 5 3 4 9 : 결과
마지막 인덱스에 가장 큰 값 찾기 완료.
loop i=1. j=1-3
1 5 3 4 9 : 인덱스 0, 1을 비교하여 정렬 (before)
1 5 3 4 9 : 인덱스 1, 2를 비교하여 정렬 swap
1 3 5 4 9 : 인덱스 2, 3를 비교하여 정렬 swap
1 3 4 5 9 : 결과
마지막 전 인덱스에 2번째 큰 값 찾기 완료.
...
(왼쪽 시작부터 버블 모양으로 비교를 한다. 이후 버블을 한 개씩 감소. )

void bubble_sort(int a[], int n){
    int i, j, t;
    for (i=0; i<n-1; i++) {
        for (j=1; j<n-i; j++){
           if (a[j-1] > a[j]){
            t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
            }
        }
    }
}

• 성능개선안: swap 교환 횟수가 0이 되면 더 이상 할필요없으므로 리턴하면 된다.

void bubble_sort(int a[], int n){
    int i, j, t;
    for (i = 0; i < n - 1; i++) {
        int bchanged=0 ;
        for (j = 1; j < n - i; j++) // j=(1,10)
        {
            if (a[j - 1] > a[j]){
                t = a[j - 1];
                a[j - 1] = a[j];
                a[j] = t;
                bchanged=1 ;
            }
        }
        if (bchanged==0) break ;
    }
}