버블정렬(Bubble Sort)
- 1. N개의 키가 왼쪽으로부터 오른쪽으로 검색되면서 모든 인접한 두 개의 키가 서로 비교된다. 인접한 두 개의 키 중에서 왼쪽의 키가 더 크면 오른쪽의 키와 자리를 바꾼다.
- A[n-1]에 가장 큰 키가 있게 된다
2. A[0:n-2]가 왼쪽으로 부터 오른쪽 방향으로 가면서 차례로 검색되는데, 이 때 역시 모든 인접한 두개의 키가 서로 비교되고 왼쪽의 키가 큰 경우에 오른쪽의 키와 자리바꿈을 한다.
- A[n-2]에 가장 큰 키가 있게 된다.
- 바로 전 단계에서 키의 자리바꿈이 일어났는지 검사
- 자리바꿈이 전혀 일어나지 않은 경우에는 배열이 이미 정렬된 것
1. 단계
2. 최악의 경우 n-1회의 단계를 거치면서 배열 전체가 오름차순으로 정렬된다.
3. 시간단축
void BubbleSort(int A[], int n)
{
int i;
bool 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;
}
}
}
}
댓글을 달아 주세요