거품*버블 정렬(Bubble Sort)

 

버블 정렬 또는 거품 정렬이라고 부른다.

 

모든 인접한 두 데이터를 차례대로 비교해서

왼쪽 데이터가 더 큰 경우에는 오른쪽 데이터와 자리를 바꾸는 과정을 반복해서 정렬을 수행하는 방식

 

출처: wikimedia commons/Bubble-sort

 

비교를 진행하는 방향

• 왼쪽에서 오른쪽으로 진행
  • 가장 큰 값을 찾아서 오른쪽 끝에 위치시킴
• 오른쪽에서 왼쪽으로 진행
  • 가장 작은 값을 찾아 왼쪽 끝에 위치시킴

 

버블 정렬 식

BubbleSort(A[], n)
{
 for(i=0; i<n-1; i++) // 단계: (n-1)번 반복
  for(j=0; j<n-1; j++) // 왼쪽에서 오른쪽으로 진행하는 경우
    if(A[j] > A[j+1]) // '왼쪽 데이터 > 오른쪽 데이터'일 경우
     A[j]와 A[j+1]의 자리 바꿈;
 return (A);
}

 

 

버블 정렬 예시(진행 방향이 왼쪽에서 오른쪽인 경우)

 

버블 정렬의 성능

 for(i=0; i<n-1; i++) // 단계: (n-1)번 반복
  for(j=0; j<n-1; j++) // 왼쪽에서 오른쪽으로 진행하는 경우

 

for문은 0, ..., (n-2)

-> (n-1) 회

 

총 두 번의 for문이 있기에 성능은 O(n²)이 된다.

 

 

버블 정렬의 특징

1. 안정적인 정렬 알고리즘
   • 인접한 두 데이터가 동일한 경우 위치 교환이 발생하지 않음
2. 제자리 정렬 알고리즘
   • 입력 배열 A[] 외 상수 개의 저장 공간만 필요
3. 선택 정렬에 비해 데이터 교환이 많이 발생

 

개선된 버블 정렬

 

버블 정렬의 성능은 반복문의 조건에서 발생한다.

 

 for(i=0; i<n-1; i++) // 단계: (n-1)번 반복
  for(j=0; j<n-1; j++) // 왼쪽에서 오른쪽으로 진행하는 경우

 

첫 번째 for문은 처리 단계의 수를 나타낸다.

자리 바꿈이 발생하지 않으면 이미 정렬된 상태이므로 이후의 처리 단계를 수행하지 않고 종료시켜야한다.

 

두 번째 for문은 인접한 두 데이터의 비교 횟수를 나타낸다.

각 단계에서 무조건 오른쪽 끝까지 이동하면서 인접한 두 데이터 비교는 불필요하다.

이때 이미 제자리를 잡은 데이터에 대해서는 비교를 수행하지 않도록 해야 한다.

 

개선된 버블 정렬 식

Advanced_BubbleSort(A[], n)
{
 for(i=0; i<n-1; i++){ // 단계: 0, 1, ..., (n-2)
  Sorted = TRUE; // 이미 정렬된 상태라고 가정
  for(j=0; j<(n-1)-i; j++) // 왼쪽에서 오른쪽으로 진행하는 경우
   if(A[j] > A[j+1]){
    A[j]와 A[j+1]의 자리바꿈;
    Sorted = FALSE; // 자리바꿈 발생 -> 미정렬 상태
   }
   if(Sorted == TRUE) break; // 이미 정렬된 상태이므로 종료
 } return (A);
}

 

개선된 버블 정렬 성능과 특징

개선된 버블정렬의 성능은 이전과 동일하게  O(n²)이다.

 

차이점은 입력 데이터의 상태에 따라 성능이 다르다는 것이다.