[Algorithm] 버블정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

버블 정렬 : 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행한다.

(데이터를 정렬하는 과정이 마치 물 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 비슷하다고 해서 버블 정렬이다!!)

 

1. 현재 배열과 다음 배열이 숫자 크기를 비교하여 더 큰 숫자를 오른쪽에 배치한다.

2. 숫자 크기 비교하여 배치가 완료된 숫자를 제외한 나머지 숫자를 1번과 같은 과정을 거친다.

3. 2번 과정을 반복한다.

 

글로 이해하려고 하면 어렵지만 직접 그려보면 개념과 코드가 금방 이해된다!

 

wikipedia ) BubbleSort

 

버블 정렬의 시간 복잡도

 

버블 정렬의 구현

public class BubbleSort {

	public static void bubbleSort(int[] a) {
    	bubbleSort(a, a.length);
    }
    
    public static void bubbleSort(int[] a, int size) {
    
    	// (배열 길이 - 1) 만큼 반복
    	for(int i = 0; i < size - 1; i++) {
        
        	// (배열 크기 - 반복 횟수)만큼 비교
            for(int j = 0; j < size - i; j++) {
            	if(a[j] > a[j + 1]) {
                	swap(a, j, j + 1);
            }
        }
    }
}

	private static void swap(int[] a, int i , int j) {
    	int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
   }
}