EunSung.log

버블 정렬

6 min read

개요

버블 정렬Bubble Sort은 정렬 알고리즘 중 하나로, 데이터의 이동 과정이 마치 물 속에서 거품(Bubble)이 보글보글 떠오르는 것과 유사하여 버블 정렬이라 부른다.

동작

버블 정렬은 인접한 2개의 데이터를 비교하여 그 크기에 따라 위치를 서로 교환하여 정렬이 이루어진다.

선택 정렬이나 삽입 정렬과 유사하게 정렬된 부분(오른쪽 리스트)과 정렬되지 않은 부분(왼쪽 리스트)으로 나누어서 사용한다.

정렬이 안된 왼쪽 리스트를 한 번 스캔하면 오른쪽 리스트의 오른쪽 끝에 가장 큰 데이터가 위치하게 되고, 오른쪽 리스트는 추가된 데이터를 포함하여 정렬된 상태가 된다.

시간 복잡도

  • 최선의 경우: 비교, 이동 없음
    • 최적화된 버블 정렬의 경우 의 비교
  • 최악의 경우: 비교, 이동
  • 평균적인 경우: 비교, 이동

분석

버블 정렬의 비교 횟수는 항상 일정하다.

최선의 경우

최선의 경우는 자료가 이미 정렬되어 있는 경우다. 이 경우에는 자료 이동이 한 번도 발생하지 않는다.

최악의 경우

최악의 경우는 자료가 역순으로 정렬되어 있는 경우다. 모든 인접 데이터가 교환되며, 각 교환마다 3회의 이동이 이뤄진다. 그러므로 총 이동 횟수는 이다.

평균적인 경우

평균적인 경우는 최선과 최악의 그 사이로, 전체 중 절반 정도에서 교환이 발생한다고 볼 수 있다. 그러므로 총 이동 횟수는 이다.

특징

  • 제자리 정렬이다.
  • 안정성을 만족한다.
  • 단점
    • 인접한 요소끼리 비교-교환하므로, 한 번에 한 칸씩만 움직일 수 있다. 즉, 비효율적으로 많이 교환해야 한다는 것이다.
    • 특정 요소가 이미 최종 정렬 위치에 있더라도 교환된다. 이 역시 비효율적으로 많은 교환 횟수를 유발한다.
  • 단순하지만, 비효율적이기 때문에 거의 쓰이지 않는다.

구현

public class BubbleSort {
	public static void sort(int[] array) {
		int n = array.length;
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - i - 1; j++) {
				if (array[j] > array[j+1]) {
					int temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				}
			}
		}
	}
}

최적화된 버블 정렬

앞서 최선의 경우의 시간 복잡도에 대해 다룰 때, “최적화된 버블 정렬의 경우 의 비교”라고 했었다.

버블 정렬은 인접한 두 데이터를 비교-교환해 정렬이 이루어진다. 위 코드를 보면 알겠지만, 1번째와 2번째 데이터를 비교-교환하고, 2번째와 3번째 데이터를 비교-교환하고, … ,번과 번째 데이터를 비교-교환한다.

즉, 교환이 한 번도 일어나지 않았다면, 그것은 이미 정렬이 완료된 상태라는 것이다.

최적화된 버블 정렬은 여기에 착안하여 교환이 한 번도 일어나지 않은 경우, 그대로 반복문을 종료시킨다. 그렇기에 최선의 경우(이미 정렬되어있는 경우) 반복문을 한 번만 돌고 끝나기 때문에 의 비교가 되는 것이다.

구현

public class OptimizedBubbleSort {
	public static void sort(int[] array) {
		int n = array.length;
		for(int i = 0; i < n - 1; i++) {
			boolean swapped = False;
			
			for(int j = 0; j < n - i - 1; j++) {
				if(array[j] < array[j+1]) {
					int temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
					swapped = True;
			}
			
			if (swapped)
				break;
		}
	}
}

참고문헌

백링크