버블정렬

[옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 방법]

직관적이고 쉽게 구현할 수 있지만 정렬 알고리즘 중에서 가장 비효율적인 알고리즘이다!
1 10 5 8 7 6 4 3 2 9   <- 두개를 한 묶음으로 비교
1 10 5 8 7 6 4 3 2 9
1 10 5 8 7 6 4 3 2 9

(1회전)
1 5 8 7 6 4 3 2 9 10 <- 가장 큰 값이 맨 뒤로 간다
                             그래서 1회전 반복때마다 반복 횟수를 줄여준다.
(2회전)
1 5 7 6 4 3 2 8 9 10

결과
1 2 3 4 5 6 7 8 9 10

구현해보자

#include <stdio.h>
int main(void) {
    int i, j, tmp;
    int arrSize = 10;
    int arr[arrSize] = {1,10,5,8,7,6,4,3,2,9};
    for (i=0; i<arrSize; i++) {

        for (j=0; j<arrSize-i; j++) {
            if (arr[j]> arr[j+1]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1]= tmp;
            }
        }
    }
    for (i =0; i<arrSize; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

[버블 정렬의 시간 복잡도 O(N^2) ]

1 10 5 8 7 6 4 3 2 9
=> 10 + 9 + … + 1
=> 10 + 9 + … + 1
=> 등차수열
=> N* (N+1)/2
=> O(N^2)

선택정렬과 동일한 시간 복잡도이지만 왜 가장 비효율적인 정렬이라 하지?

선택정렬은 가장 작은 데이터를 골라 마지막에 자리 이동을 한다.
즉, 1회전에 자리이동 1회
버블정렬은 매번 교체를 해줘야하기 때문에 더 오랜 시간이 걸린다.
즉, 1회전에 자리이동 여러번
그래서 정렬중 가장 비효율적 정렬이라 함!

References
https://www.youtube.com/watch?v=EZN0Irp2aPs&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=3