정렬 (4) - 버블 정렬 (Bubble Sort)

1. 알고리즘 개요

• 인접요소의 비교/교환을 통해 최대값을 제일 뒤로 보낸다
• 시간 복잡도 : $O(n^2)$
• 특징 : 뒷쪽부터 정렬된다는 특징이 있고, 교환횟수가 매우 많아 느리다.

 

[그림] 버블정렬 애니메이션

 

2. 소스코드

void bubble_sort(int *arr, int size){
	
	for(int i = 0 ; i < size - 1 ; i++){
    // 마지막 칸은 자동 정렬되니까 size - 1 까지
		
		for(int j = 0 ; j < size - i - 1; j++){
		// 전체 루프 size - 1에서 정렬된 i 전까지 
        
			if(arr[j] > arr[j+1]){
				
				swap(&arr[j], &arr[j+1]);	
			}
		}
	}
}

 

3. Reference