Bubble Sort

개요

두 인접한 원소를 정렬해 나간다.

구현은 쉬우나 효율은 좋지 않은 편에 속한다. 대충 이런 정렬이 있구나 하고 알고 넘어가면 된다.

 

55 07 78 12 42  초기값[파란색은 sorting]
07 55 78 12 42  첫 번째 패스(pass)
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78  두 번째 패스(pass)
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78  세 번째 패스(pass)
07 12 42 55 78  네 번째 패스(pass)
07 12 42 55 78  다섯 번째 패스(pass)
07 12 42 55 78  정렬 끝

 

 

시간 복잡도

n-1, n-2, ... 1번을 반복하게 되며 이를 식으로 나타내면 n(n-1)/2이므로, O(n^2)이다.

 

 

 

 

 

오른쪽->왼쪽도 가능하다.

 

 

코드

void bubble_sort(int* p, int size) { 
	for (int i = 0; i < size - 1; i++) { 
		for (int j = 0; j < size - i - 1; j++) { 
			if (p[j] > p[j + 1]) { 
				swap(p[j], p[j + 1]); 
			}
		}
	}
}

 

 

ref

https://todaycode.tistory.com/46

버블 정렬이란?