버블정렬 (Bubble Sort)

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내자

버블정렬 또한 선택정렬과 같이 비효율적인 정렬 방법중 하나다.

버블정렬이 선택정렬보다 연산량이 많다

 

 

 

  

 

 

 

 

 

버블정렬(Bubble sort)시간복잡도

n-1, n-2, ..... , 2, 1 = n(n-1)/2

T(n)=O(n^2)

 

정렬 알고리즘 시간 복잡도

Name	Best	Avg	Worst	Run-time (int 60,000) sec
버블정렬	n^2	n^2	n^2	22.89
선택정렬	n^2	n^2	n^2	10.84
삽입정렬	n	n^2	n^2	7.43
셀정렬	n	n^1.5	n^2	0.05
퀵정렬	nlog₂n	nlog₂n	n^2	0.01
힙정렬	nlog₂n	nlog₂n	nlog₂n	0.03
병합정렬	nlog₂n	nlog₂n	nlog₂n	0.02

 

 

 

 

#include<stdio.h>
#define MAX_SIZE 5

void bubble_sort(int list[], int n)
{
    int i, j, temp;

    for (i = n - 1; i > 0; i--)
    {
        for (j = 0; j < i; j++)
        {
            if (list[j] < list[j + 1]) 
            {
                temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
}

int main()
{
    int i;
    int n = MAX_SIZE;
    int list[] = { 7,4,5,1,3 };

    bubble_sort(list, n);

    for (i = 0; i < n; i++)
    {
        printf("%d", list[i]);
    }
}