47. 더 나은 버블정렬

더 나은 버블정렬이란?

버블 정렬에서 성능 개선을 위해 이미 정렬된 배열을 인지하고 정렬을 중단하는 기능을 추가한 것이다.

이전 포스팅에서 보았던 것처럼 일반적인 버블정렬은 모든 요소를 반복적으로 비교하고 교환한다.

즉, 이미 정렬된 리스트에 대해서도 불필요한 반복과 교환작업이 수행되기 때문에 성능이 낮을 수 있다.

 

동작 방식

1. 리스트의 첫 번째 요소부터 마지막 요소까지 반복하면서 인접한 두 요소를 비교한다.

2. 만약 두 요소가 순서대로 정렬되어 있다면(Flag == True) 비교를 건너뛴다.

3. 만약 두 요소의 순서가 정렬되어있지 않다면(Flag == False) 위치를 교환하고 Flag를 False로 설정한다.

4. 리스트를 한 번 순회한 후, Flag가 True라면 이미 정렬된 상태이므로 정렬을 중단한다.

 

이처럼 Flag를 사용하여 이미 정렬된 부분을 인지하고 반복을 제한함으로써 성능을 개선할 수 있다.

Flag를 사용한 버블정렬의 시간 복잡도는 최선의 경우 O(n)이 될 수 있다.

---

#define SWAP(a,b,t) ((t=a), (a=b), (b=t))

void Bubble_Flag(int User_Data[], int n){
	int i, j, flag=n-1, temp;
	
	// flag가 0이라면 정렬이 이미 완료된 것 
	while(flag > 0){
		// 교환이 일어난 자리까지 다시 정렬해야하므로 flag까지이다. 
		for(i=0,j=0; i < flag; i++)
			if(User_Data[i+1] < User_Data[i]){
				SWAP(User_Data[i], User_Data[i+1], temp);
				// 교환이 일어난 자리를 저장 
				j=i;
			}
		// 교환이 일어난 자리까지 다시 정렬을 하므로 그 값을 flag에 저장 
		flag = j;
	}
}