버블 정렬(Bubble sort)

: 인접한 두 원소끼리 비교해, 크기가 순서대로 되어있지 않으면 두개를 바꾼다.

• 기본적으로 O(n^2) 시간복잡도를 갖는다.

  • 그냥 무조건 for문 두번 돌기 때문에 최악, 평균 이런거 없이 다 O(N^2)

• 선택정렬과 기본 개념이 유사

• 장점: 간단하다

• 단점: 특정 요소가 최종 정렬 위치에 있어도 교환하는 일이 일어날 수 있다.

소팅 과정

: 예시로 보는 것이 직관적. 오름차순의 경우를 예시

• 1회전(1번 루프) [6 4 9 7 2 5] -> [4 6 9 7 2 5] -> [4 6 9 7 2 5] -> [4 6 7 9 2 5] -> [4 6 7 2 9 5] -> 최종 [4 6 7 2 5 9]
• 2회전 [4 6 7 2 5 9] -> [4 6 7 2 5 9] -> [4 6 7 2 5 9] -> [4 6 2 7 5 9] -> 최종 [4 6 2 5 7 9]
• 3회전 [4 6 2 5 7 9] -> [4 6 2 5 7 9] -> [4 2 6 5 7 9] -> 최종 [4 2 5 6 7 9]
• 4회전 [4 2 5 6 7 9] -> [2 4 5 6 7 9] -> 최종 [2 4 5 6 7 9]
• 5회전 [2 4 5 6 7 9] -> 최종 [2 4 5 6 7 9]

코드

void bubbleSort(int data[], int size) {
    for(int i = size - 1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            if(data[j] < data[j + 1]) {
                int tmp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = tmp;
            }
        }
    }
}

Reference)

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html