[Sort] 버블정렬 Bubble Sort

버블정렬 Bubble Sort

✏️개념

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

• 선택정렬과 유사

• 첫번째와 두번째, 두번째와 세번째, 세번째와 네번째…이런 식으로 비교하며 한 회전당 맨 뒤 하나씩 fix해 나간다.

• 예제

✏️C코드 구현

bubbleSort(a[n], n){
    int tmp;

    for(int i = n-1; i > 0; i--){
        for(int j = 0; j < i; j++){
            if(a[j+1] < a[j]){
                tmp = a[j-1];
                a[j-1] = a[j];
                a[j] = tmp;
            }
        }
    }
}

✏️시간복잡도

• 이 버블정렬 알고리즘은 중첩된 두 개의 for 루프에서 n(n-1)/2번의 비교 연산을 해야하기 때문에 시간 복잡도는 O(n^2)이 된다.