기본 개념
-
버블 정렬 알고리즘은 여러 단계로 나누어진다.
-
첫째 단계에서 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 회의 자리바꿈이 발생한다
-
키 사이의 자리바꿈이 발생하지 않고 상수 개의 변수만이 여분으로 필요하므로 안정적인 제자리 정렬이다
참고 : 알고리즘 - 이한출판사
'알고리즘스터디' 카테고리의 다른 글
[알고리즘] 힙 정렬 (Heap Sort) (0) | 2020.08.19 |
---|---|
[알고리즘] 쉘 정렬 (Shell Sort) (0) | 2020.08.10 |
[알고리즘] 퀵 정렬 (Quick Sort) (0) | 2020.08.10 |
[알고리즘] 삽입정렬 (Insertion Sort) (0) | 2020.08.03 |
[알고리즘] 선택정렬 (Selection Sort) (0) | 2020.08.03 |