버블 정렬(Bubble Sort)

버블 정렬이란?

가장 왼쪽 원소부터 바로 오른쪽에 있는 원소와 비교해 가면서 큰수가 오른쪽으로 가도록 교환하는 것이다.

가장 오른쪽까지 가면 가장 큰 원소를 찾은것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복하는 정렬 방법이다.

시간복잡도는 (n-1) + (n-2) + … + 1 = n(n-1)/2 = Θ(n^2) 즉, O(n^2)이다. 

버블 정렬 코드를 보면

첫번째 for문에서 i < n - 1은 결국 4 3 2 1이 있다면

첫번째 배열과 두번째 배열, 두번째 배열과 세번째 배열, 세번째 배열과 네번째 배열 

총 3번 비교하는 것이기에 최대수 - 1인 것을 의미한다.

두번째 for문에서의 j < (n - i) - 1은 정렬이 완료될 때 마다 i가 1씩증가하여 정렬이 완료된 것을 빼주는 역할을 한다.

#include <stdio.h>
 
void BubbleSort(int arr[], int n)
{
    int i, j;
    int temp;
    
    for(i = 0 ; i < n - 1; i++)
    {
        for (j = 0; j < (n - i) - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
 
int main()
{
    int arr[4] = { 3, 2, 4, 1 };
    int i;
    
    BubbleSort(arr, sizeof(arr) / sizeof(int));
 
    for (i = 0; i < 4; i++)
        printf("%d ", arr[i]);
 
    return 0;
}
 
//                                                        If you want to see more? click here >>