버블정렬(Bubble Sort, Sinking Sort)이란 무엇일까?

버블정렬

• 두 인접한 원소를 비교하여 정렬하는 방법
• 시간 복잡도가 O(n^2)로 상당히 느리다
• 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

버블정렬은 이해하기 쉽고 코드도 간단하지만 시간복잡도 때문에 비교할 데이터의 개수가 많아질수록 성능이 저하됩니다.

이해를 돕는 영상

 

 

[C++]

int* bubble_sort(int arr[], int n) {
    int i, j, temp;
    for (i=n-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;
            }
        }
    }
    return arr;
}