C언어 - 버블 정렬 (Bubble Sort), 버블 정렬 개선

파도타듯 두 값씩 정렬해가면서 큰 수를 맨 뒤로 보내면서 채워간다

마지막 수를 제외하고 다시 처음부터 반복하여 비교하며 정렬하는 알고리즘이다.

 

순차 정렬, 버블 정렬, 선택 정렬 세 정렬은 코드는 단순하나 컴퓨터 입장에서 비효율 적이여서 싫어하는 정렬이다. 비교대상이 30개 미만일 경우 사용하기에 좋다.

 

비교 횟수는 n-1 -> n-2 -> n-3 -> ... -> n-n+3 -> n-n+2 -> n-n-1 순으로 값이 줄어들며 비교된다.

 

비교하는 값은 노란색

정렬후 값은 보라색

 

 

---

핵심 알고리즘

---

void BubbleSort(int *arr,int n, int i, int j){
    for(i=n-1; i>0; i--){
        for(j=0; j<i; j++){
            if(arr[j] > arr[j+1]){
                swap(&arr[j],&arr[j+1]);
            }
        }
    }
}

 

코드

---

# include <stdio.h>

void BubbleSort(int *arr, int n, int i, int j);
void printarr(int *arr, int n, int i, int j);
void swap(int *a,int *b);

int main(){
  int arr[] = {7,2,4,8,6};
  BubbleSort(arr,5,0,0);

  return 0;
}

void BubbleSort(int *arr,int n, int i, int j){
    printarr(arr, n, n, -2);
    for(i=n-1; i>0; i--){
        for(j=0; j<i; j++){
            printarr(arr, n, i, j);
            if(arr[j] > arr[j+1]){
                swap(&arr[j],&arr[j+1]);
            }
        }
    }
    printarr(arr, n, -1, j);
}

void printarr(int *arr, int n, int i, int j) {
    int text=0;
    for(int c = 0; c<n; c++) {
        if ( c > i) {
            printf("\x1b[35m");
        }
        else if ( c == j || c == j+1) {
            printf("\x1b[33m");
        }
        else{
            printf("\x1b[37m");
        }
        printf(" %d ", arr[c]);
    }
    printf("\n");
}

void swap(int *a,int *b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

 

---

 

버블 정렬 개선

---

버블 정렬에서 만약 정렬해야하는 수의 배열이 정배열이여서 정렬이 필요가 없을경우를 대비해서 개선되었다.

보면 정렬하는 횟수가 확 줄었다. 지금은 5개의 수를 정렬해서 그렇게 크진 않지만 1억개 수천억개를 정렬할때는 차이는 엄청날것이다.

 

 

핵심 알고리즘

---

void BubbleSort(int *arr,int n, int i, int j){
    int check;
    for(i=n-1; check&&i>=1; i--){
        check = 0;
        for(j=0; j<i; j++){
            if(arr[j] > arr[j+1]){
                swap(&arr[j],&arr[j+1]);
                check = 1;
            }
        }
    }
}

 

변수 check 를 선언해 정렬이 필요 없는 수의 나열이면 필요없는 비교를 멈춰준다.