Bubble sort (버블 정렬)

버블 정렬

    - 두 인접한 요소를 검사하여 정렬

 

 

 

동작

    - 오름차순으로 정렬

    - 1회 

        * 1번째 요소와 2번째 요소를 비교하고 순서가 맞지 않으면 교환

        * 2번째 요소와 3번째 요소를 비교하고 순서가 맞지 않으면 교환

        * n-1번째 요소와 n번째 요소를 비교하고 순서가 맞지 않으면 교환

        * n번째에 가장 큰 요소가 위치

 

    - 2회 

        * 1번째 요소와 2번째 요소를 비교하고 순서가 맞지 않으면 교환

        * 2번째 요소와 3번째 요소를 비교하고 순서가 맞지 않으면 교환

        * n-2번째 요소와 n-1번째 요소를 비교하고 순서가 맞지 않으면 교환

        * n-1번째에 두 번째로 큰 요소가 위치

 

    - 이하 과정 동일

 

    - 예시

 

https://en.wikipedia.org/wiki/Bubble_sort

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

 

구현

void bubble_sort(int list[], int n){
    
    int i, level, tmp;
    
    // 배열 전체를 순회하는 횟수  
    for(level = 0; level < n -1; level++){
        // 1회 순회할 때, 각 요소들 비교 
        for(i=0; i<n -level -1; i++){
            // 오름차순으로 정렬하기 위해 교환  
            if(list[i] > list[i+1]){
                tmp = list[i+1];
                list[i+1] = list[i];
                list[i] = tmp;
            }
            
        }
    }
    
} 

 

 

특징

    - 안정한 정렬

    - 1회 순회하면 최댓값/최소값이 맨 뒤에 위치

    - 이미 맨 끝에 최댓값/최소값이 위치하더라고 인접한 요소들을 비교하고 교환하기 때문에 느림

    - swap은 move보다 더 복잡하기 때문에 오래 걸림

 

    - 시간복잡도

       * 평균 : O(N^2)

 

 

 

참조

    - 블로그 1

    - 블로그 2

    - 위키피디아 1

    - 위키피디아 2