cpp) 버블정렬, Bubble Sort

 

- 버블정렬

 

배열의 앞에서부터, 인접한 두 요소끼리 비교하여 자리를 교체하는 방식

 

이를 반복하다보면 배열의 마지막 자리에 가장 큰 요소가 위치하며 정렬되는데,

이것이 거품이 올라오는 듯 하다해서 '버블' 정렬

 

 

- 절차(오름차 기준)

• 길이  n의 배열의 0번부터 n-1번까지, 인접 요소끼리 비교, 자리를 적절히 교체 -> 가장 큰 요소가 마지막에 위치
• 0번부터 n-2번까지 인접 요소 비교, 교체
• 0번부터 n-3...반복
• 배열의 요소가 하나(0번)만 남을때 까지 수행한다.

 

- 시간복잡도

 

최악,최선, 평균 모두 사이클 당 비교 횟수가 n-1번,n-2번...

T(n) = (n-1)+(n-2)...2+1 = (n-1)*n/2

O(n) = n^2

 

 

- 특징

 

정렬에 사용하는 외부 메모리 X 

이를 In-place sort라고 한다.

 

 

- 코드

 

#include <iostream>
using namespace std;

void bubble(int *arr,int len){
    
    int i,j,temp;

    for(i = len-1; i >= 0; i--){
        for(j = 0; j < i; j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    
    for(i = 0; i < len; i++){
        cout << arr[i] << endl;
    }
}

int main() {
    int n;
    cin >> n;

    int *arr = (int *)malloc(sizeof(int) * n);
    
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    bubble(arr,n);

    free(arr);
    return 0;
}

백준 2750번 참고 2750번: 수 정렬하기 (acmicpc.net)