[알고리즘] 버블 정렬(Bubble Sort) - 코딩밥상

버블 정렬이란?

버블 정렬이란 이름은 물 속 깊은 곳에서 수면을 향호 올라오는 거품들의 모습처럼 데이터를 정렬하기에 붙여진 이름입니다.

즉 자료구조를 순회하면서 이웃한 요소들끼리 데이터를 교환하며 정렬을 수행합니다.

이웃한 요소끼리 데이터를 교환하므로 교환 전에 먼저 이웃끼리 비교하여 바른 순서로 위치해 있는지 확인해야 합니다.

 

예를들어

5 1 6 4 2 3 을 오름차순으로 버블정렬 하면,

5 1 6 4 2 3 -> 1 5 6 4 2 3 -> 1 5 4 6 2 3 -> 1 5 4 2 6 3 -> 1 5 4 2 3 6

1 5 4 2 3 6 -> 1 4 5 2 3 6 -> 1 4 2 5 3 6 -> 1 4 2 3 5 6

1 4 2 3 5 6 -> 1 2 4 3 5 6 -> 1 2 3 4 5 6

1 2 3 4 5 6 -> 1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

위 과정처럼 이웃한 숫자끼리 비교하여 조건에 맞게 자리를 바꿔주며 끝 지점 값을 확정시킵니다.

그 다음 과정에서부터도 똑같이 이웃한 숫자들을 비교하여 바꿔주며 또 다른 끝 지점 값을 확정시킵니다. 

 

버블 정렬은 시간복잡도 O(n^2) 으로 매우 비효율적이지만

구현이 쉽습니다.

---

코드 구현

void BubbleSort(int DataSet[], int Length){
    int temp = 0;
    
    for(int i=0; i<Length-1; i++){
        for(int j=0; j<Length-(i+1); j++){
            if(DataSet[j] > DataSet[j+1]){
                temp = DataSet[j+1];
                DataSet[j+1] = DataSet[j];
                DataSet[j] = temp;
            }
        }
    }
}