티끌 모아 태산

기본 개념

• 버블 정렬 알고리즘은 여러 단계로 나누어진다.

• 첫째 단계에서 n 개의 키가 왼쪽으로부터 오른쪽으로 검색되면서 모든 인접한 두 개의 키가 서로 비교된다.

• 인접합 두 개의 키 중에서 왼쪽의 키가 더 크면 오른쪽의 키와 자리를 바꾼다.

• 첫째 단계가 완료되었을 때 n개의 키중에서 가장 큰 키가 오른쪽 끝으로 옮겨져 A[n-1] 에 있게 된다.

• 두 번째 단계에서는 A[0:n-2] 가 왼쪽으로부터 오른쪽 방향으로 가면서 차례로 검색된다

• 역시 모든 인접한 두개의 키가 서로 비교되고 왼쪽의 키가 큰 경우에 오른쪽 키와 자리바꿈 한다

• 두 번째 단계가 끝나면 두 번째로 큰 키가 A[n-2]에 자리하게 된다.

• 최악의 경우 이러한 단계를 n-1회를 거치면 배열 전체가 오름차순으로 정렬된다.

• 실행 시간 단축을 위해 한 단게를 시작하기 전에 바로 전의 단계에서 키의 자리바꿈이 일어났는지 검사하여 자리바꿈이 전혀 일어나지 않은 경우에는 배열이 이미 정렬된 것이므로 다음 단계를 생략한다.

시간복잡도 O(n^2) 

공간복잡도 O(n)

알고리즘

void BubbleSort(int A[], int n)
/*입력 : A[0:n-1] - 정렬한 원소가 있는 배열, n - 정렬할 원소의 개수.
  출력 : A[0:n-1] : 정렬된 배열. */
  int i, Sorted;
  Sorted = false;
  while(!Sorted){
  		Sorted=True;
        for(i=1;i<n;i++)
        	if(A[i-1] > A[i]){
            	Swap(&A[i-1], &A[i]);
                Sorted=false;
            }
  	}
}    

• 주어진 키가 모두 내림차순으로 이미 정렬되어 있는 경우 최악의 실행시간을 보인다

• 모든 경우의 단계를 거쳐야만 정렬이 완료되므로 n(n-1)/2회의 비교를 하게 된다

• 이 때 비교를 할 때마다 n(n-1)/2 회의 자리바꿈이 발생한다

• 키 사이의 자리바꿈이 발생하지 않고 상수 개의 변수만이 여분으로 필요하므로 안정적인 제자리 정렬이다

참고 : 알고리즘 - 이한출판사