[lecture] 6주차.정렬 알고리즘_버블 정렬

버블 정렬(Bubble Sort)

버블 정렬은 이웃하는 숫자를 비교해 작은 수를 앞쪽으로 이동시키는 과정을 반복해 진행하는 정렬이다. 이 모습이 마치 버블과 같아 그러한 이름이 붙였다.

패스(pass)

버블 정렬에는 입력을 전반적으로 1번 처리하는 것을 패스라고 한다.

n 개의 원소가 있다면 (n-1)번 패스를 수행하게 된다.

//Bubble sort
입력 : 크기가 n인 배열 A
출력 : 정렬된 배열 A
for pass=1 to n-1
	for i=1 to n-pass
    	if(A[i-1] > A[i])	//위의 원소가 아래의 원소보다 크다면
        	A[i-1] <-> A[i]	//자리 바꾸기
return A

시간 복잡도

버블 정렬은 for 루프 속에서 for 루프를 수행하게 되는데 pass가 1인 경우 n-1 번 비교하게 되고 따라서 총 비교 횟수는 (n-1) + (n-2) ... + 1 = n(n-1) / 2이다. 안쪽 for 루프의 if 조건이 true일 때의 자리 바꿈은 O(1)이다. n(n-1) / 2 * O(1)을 계산하면 시간 복잡도는 O(n^2) * O(1) = O(n^2)이다.