[알고리즘] 02 버블 정렬(Bubble Sort)

버블 정렬

 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(bubble) 정렬이라고 함

 

수행 방법

• 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
• 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬됨

 

버블정렬이 진행되는 과정(1)

버블정렬이 진행되는 과정(2)

버블정렬이 진행되는 과정(3)

수행 시간: θ(n^2)

• 첫 for 루프는 n-1번 반복
• 두번째 for 루프는 각각 i-1, i-2, …, 2, 1번 반복
• 원소 교환은 상수 시간 작업

 

코드 구현

public class Sort {
	public void bubbleSort(int[] a) {
		int size = a.length;
		for (int i = size - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (a[j] > a[j + 1]) {
					swap(a, j, j + 1);
				}
			}
		}
	}
	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}