버블 정렬

 

버블 정렬: 옆에 있는 값과 비교해서 작은 값을 앞으로 보내기

사이클이 돌때마다 가장 큰 값이 맨뒤로 이동하게 된다.

Ex)

     1 10 5 8 7 6 4 3 2 9

     1 5 8 7 6 4 3 2 9 10

     1 5 7 6 4 3 2 8 9 10

      ~

     1 2 3 4 5 6 7 8 9 10

 

시간 복잡도 : O(N^2)

 

구현은 쉬우나 가장 비효율적인 정렬 알고리즘.

 

실제로 선택정렬과 시간 복잡도는 같으나 수행 시간이 더 오래걸리는 이유

선택 정렬은 최솟값을 선택하여 마지막에만 스왑을 하지만 버블 정렬의 경우 비교 연산과 스왑을 사이클마다 수행하므로 연산 횟수가 사실상 훨씬 더 많아진다.

 

#include <stdio.h>

int main()
{
	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++) 
		{ // 큰 값이 뒤로 이동하면서 집합의 크기가 하나씩 감소되므로 9 - i 
			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;
}