알고리즘 - 정렬 1.2 버블 정렬

버블 정렬 정의

: 모든 인접한 두 데이터를 차례대로 비교해서 왼쪽 데이터가 더 큰 경우 오른쪽 데이터와 자리를 바꾸는 과정을 반복해서 정렬을 수행하는 방식.

 

int BubleSore(A[], n)
{
	for(i=0; i < n-1; i++){			//단계 : (n-1)회 반복
    	for(j=0; j < n - 1; j++){	//좌측에서 우측으로 진행
        	if(A[j] > A[j+1]){		//좌측 데이터 > 우측 데이터 일 경우
            imt tmp = A[j]
            A[j] = A[j+1]
            A[j+1] = tmp
        }
    }
    return (A)
}

 

성능 => O(n^2)

안정적인 정렬 알고리즘

제자리 정렬 알고리즘

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

 

따라서 개선된 버블정렬이 나타남

각 루프의 반복 회수를 줄여나가는 것.

 

Advanced_BubleSore(A[], n){
	for(i=0; i < n -1; i++){			
    	soretd = true;					// 정렬 상태라고 가정
        for(j=0; j < (n - 1) - i; j++){ // 우측형 진행
        	if(A[j] > A[j+1]) {
            	tmp = A[j]
                A[j] = A[j+1]
                A[j+1] = tmp
                sorted = false;			// 자리 바꿈이 발생 했다라는 것 -> 미정렬 상태
            }
        }
        if(sorted == true) break;		// 이미 정렬된 상태이므로 종료
    }
    return A
}

 

성능 => 최악 O(n^2) 최선 O(n)

하지만 입력된 데이터의 상태에 따라 성능이 달라짐

 

역순 정렬의 경우 (정렬 완료 붉은색)

0 50 40 30 20 10

1 40 30 20 10 50

2 30 20 10 40 50

3 20 10 30 40 50

4 10 20 30 40 50

=> 최악 O(n^2)

 

최선 정렬의 경우

0 10 20 30 40 50

1 10 20 30 40 50

 

=> 최선 O(n)