[C언어] 버블 정렬(Bubble Sort)

정렬 알고리즘의 일종.

성능이 몹시 구리다.

비교해야하는 데이터의 크기가 N개라고 치면 총 N(N-1)/2 번 의 비교가 수행됨 

-----------------------------------------

#include <stdio.h>
 
// 총 비교 횟수 = (n-1) + (n-2) + (n-3) + .... + 3 + 2 + 1 
 
void BubbleSort(int DataSet[],int Length){
    int i=0,j=0,temp=0;
 
    for(i=0;i<Length-1;i++){ // 총 몇번 전체 틀이 돌아갈 것이냐 (총 항의 갯수)
        for(j=0;j<Length-(i+1);j++){ // 한번의 틀 당 총 몇번의 비교를 할 것이냐 (각 항의 숫자)
            if(DataSet[j]>DataSet[j+1]){
                temp=DataSet[j];
                DataSet[j]=DataSet[j+1];
                DataSet[j+1]=temp;
            }
        }
    }
 
}
 
 
 
int main(){
    int DataSet[]={6,4,2,3,1,5};
    int Length=sizeof(DataSet)/sizeof(DataSet[0]);
    int i=0;
 
    BubbleSort(DataSet,Length);
 
    for(i=0;i<Length;i++){
        printf("%d ", DataSet[i]);
    }
    printf("\n");
 
    return 0;
}

실행 결과

=======================================================================

※비타민 퀴즈 

이미 정렬되어 있는 경우엔 루프를 취소하고 빠져나오도록 알고리즘을 개선하세요 

#include <stdio.h>
 
// 총 비교 횟수 = (n-1) + (n-2) + (n-3) + .... + 3 + 2 + 1 
 
int flag=0;
 
void BubbleSort(int DataSet[],int Length){
    int i=0,j=0,temp=0;
 
    for(i=0;i<Length-1;i++){ // 총 몇번 전체 틀이 돌아갈 것이냐 (총 항의 갯수)
        for(j=0;j<Length-(i+1);j++){ // 한번의 틀 당 총 몇번의 비교를 할 것이냐 (각 항의 숫자)
            if(DataSet[j]>DataSet[j+1]){
                temp=DataSet[j];
                DataSet[j]=DataSet[j+1];
                DataSet[j+1]=temp;
                flag=1;
            }
        }
        //비타민퀴즈 : 이미 정렬되어있으면 루프 취소하고 빠져나오게끔 버블 알고리즘을 개선하라 
        if(flag==0){
            printf("이미 정렬되어있는 배열입니다.\n");
            return;
        }
    }
 
}
 
 
 
int main(){
    int DataSet[]={1,2,3,4,5,6};
    int Length=sizeof(DataSet)/sizeof(DataSet[0]);
    int i=0;
 
    BubbleSort(DataSet,Length);
 
    for(i=0;i<Length;i++){
        printf("%d ", DataSet[i]);
    }
    printf("\n");
 
    return 0;
}