버블 정렬(Bubble Sort)

🟩 왼쪽에서 오른쪽 방향으로 인접한 두 개의 숫자를 비교해 교환하여 정렬

오름차순으로 정렬될 때까지 다시 돌아와 반복한다.

반대 방향으로도 가능

BubbleSort(A[ ], n) {
	for (i=0; i< n-1; i++) // 단계: (n-1)번 반복
		for (j=0; j < n-1; j++) // 왼쪽에서 오른쪽으로 진행하는 경우
			if (A[j] > A[j+1]) // ‘왼쪽 데이터 >오른쪽 데이터’이면
		A[j]와 A[j+1]의 자리바꿈;
	return (A);
}

 

🟩 시간 복잡도

for문 i (외부 반복문) : 0 ~ (n-2) 👉 (n-1)회

for문 j (내부 반복문) : 동일 👉 (n-1)회

총 비교 횟수 = O(n^2)

 

🟩 성능

선택 정렬에 비해 데이터 교환이 많이 발생. 선택 정렬보다 비효율적

👉 각 루프의 반복 횟수를 줄여 개선 가능하다.

 

🚀 개선된 버블 정렬

외부 반복문 = 처리 단계의 수

자리바꿈이 발생하지 않으면 이미 정렬된 상태이므로 이후의 처리 단계를 수행하지 않고 종료

 

내부 반복문 = 인접한 두 데이터의 비교 횟수

각 단계에서 무조건 오른쪽/왼쪽 끝까지 이동하면서 인접한 두 데이터의 비교가 불필요

👉 이미 제자리를 잡은 데이터에 대해서는 비교를 수행하지 않도록 한다.

Advanced_BubbleSort(A[ ], n) {
	for (i=0; i< n-1; i++) { // 단계: 0, 1, ⋯, (n-2)
		Sorted= TRUE;// 이미 정렬된 상태라고 가정
		for (j=0; j < (n-1)-i; j++) // 왼쪽에서 오른쪽으로 진행하는 경우
			if (A[j] > A[j+1]) {
				A[j]와 A[j+1]의 자리바꿈;
				Sorted= FALSE;// 자리바꿈 발생 → 미정렬 상태
			}
			if (Sorted== TRUE) break;// 이미 정렬된 상태이므로 종료
	} 
    return (A);
}

 

🟩 개선된 버블 정렬의 시간복잡도

O(n^2)로 동일

 

cf. 역순으로 정렬된 경우(최악의 경우) : O(n^2)

cf. 원하는 순서로 이미 정렬된 경우 : O(n)