[알고리즘] 버블 정렬

버블 정렬

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다.

버블 정렬은 단 두 개의  요소만 정렬해주는 좁은 범위의 정렬에 집중한다.

접근법 자체는 간단하지만, 단 하나의 요소를 정렬하기 위해 너무 많은 교환이 발생할 수 있다.

 

 

 

---

예를 들어 

 

6 3 8 5 2 7 4 1 

 

이라는 숫자를 오름차순으로 정렬한다고 가정해보자.

 

우선 가장앞의 6 과 3을 비교해서 순서를 바꾼다.

 

3 6 8 5 2 7 4 1 

 

이제 6 과 8을 비교해보면 교환할 필요가 없으므로 그대로 두고

바로 다음에 있는 쌓인 8과 5를 비교해서 순서를 바꾼다.

 

3 6 5 8 2 7 4 1

 

이런식으로 끝까지 진행한다면

 

3 6 5 2 7 4 1 8 

 

위와 같이 정렬된다.

 

 

하지만 아직 오름차순으로 정렬이 되지 않았기 때문에, 다시 처음부터 동일한 작업을 반복한다.

 

이 과정을 반복하다보면 최종적으로는 아래와 같이 오름차순 정렬이 된다.

 

1 2 3 4 5 6 7 8

 

이러한 방식을 버블정렬이라고 한다.

 

한번 수행 할 때 마다 맨 뒤의 숫자는 정렬된다는 특징이 있다.

고로 수행시 마다 수행해야 할 인덱스가 1개 씩 줄어든다.

 

#include <stdio.h>

#define SIZE 8

int main()
{
    int temp;
    
    int arr[SIZE] = {6,3,8,5,2,7,4,1}; 


    
    for(int i = 0; i < SIZE -1; i++) //(n-1)...(n-2)..(n-3)..이런 식으로 전체를 정렬해야 하는 횟수가 줄어듬
    {                          //   왜냐. 한번 정렬시에 마지막 숫자 8은 이미 정렬 되어있음
        for(int j = 0; j < (SIZE-1) - i; j++){ //인덱스 번호 비교를 위한 반복문
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }



    for(int i = 0; i < 8; i++)
    {
        printf("%d ", arr[i]);
        
    }
    
    return 0;
}

#include <stdio.h>

int main(void)
{
    int i, j , temp;
    int array[10] = {1,10,5,8,7,6,4,3,2,9};
    for(i = 0; i < 10; i++)
    {
        for(j = 0; j < 9-i; j++)
        {
            if(array[j] > array[j+1])
            {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        } 
    }

    for(i = 0; i < 10; i++)
    {
        printf("%d ", array[i]);
    }
    return 0;
}

 

 

이러한 버블 정렬의 Big O 는 선택정렬과 마찬가지로 등차수열에 따라서 

O(N^2) 가 된다.