[알고리즘] 정렬 알고리즘 - 버블 정렬 Bubble Sort

버블 정렬 (Bubble Sort) 알고리즘 : 

서로 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬 알고리즘

요소의 개수가 n개인 배열은 총 n-1회의 패스를 거치며, i번째 패스에서 각각 n-i번의 정렬을 수행한다

( 패스의 횟수가 n-1회인 이유는 n-1회의 정렬이 끝나면 마지막 요소 하나가 남는데, 이미 정렬된 상태이기 때문 )

 

int[] bubble = {6, 4, 5, 1, 2}

1. 첫번째 패스 : bubble[0] ~ bubble[4] 중 가장 큰 요소가 맨 뒤로 이동

   1-1. bubble[0]과 bubble[1]을 비교, bubble[0]이 bubble[1]보다 크므로 교환 {4, 6, 5, 1, 2}

   1-2. bubble[1]과 bubble[2]을 비교, bubble[1]이 bubble[2]보다 크므로 교환 {4, 5, 6, 1, 2}

   1-3. bubble[2]과 bubble[3]을 비교, bubble[2]이 bubble[3]보다 크므로 교환 {4, 5, 1, 6, 2}

   1-4. bubble[3]과 bubble[4]을 비교, bubble[3]이 bubble[4]보다 크므로 교환 {4, 5, 1, 2, 6}

2. 두번째 패스 : bubble[0] ~ bubble[3] 중 가장 큰 요소가 맨 뒤로 이동

   2-1. bubble[0]과 bubble[1]을 비교, bubble[0]이 bubble[1]보다 작으므로 교환X {4, 5, 1, 2, 6}

   2-2. bubble[1]과 bubble[2]을 비교, bubble[1]이 bubble[2]보다 크므로 교환 {4, 1, 5, 2, 6}

   2-3. bubble[2]과 bubble[3]을 비교, bubble[2]이 bubble[3]보다 크므로 교환 {4, 1, 2, 5, 6}

 

 

배열 bubble의 버블 정렬 과정 - 1

 

3. 세번째 패스 : bubble[0] ~ bubble[2] 중 가장 큰 요소가 맨 뒤로 이동

   3-1. bubble[0]과 bubble[1]을 비교, bubble[0]이 bubble[1]보다 크므로 교환 {1, 4, 2, 5, 6}

   3-2. bubble[1]과 bubble[2]을 비교, bubble[1]이 bubble[2]보다 크므로 교환 {1, 2, 4, 5, 6}

4. 네번째 패스 : bubble[0] ~ bubble[1] 중 가장 큰 요소가 맨 뒤로 이동

   3-1. bubble[0]과 bubble[1]을 비교, bubble[0]이 bubble[1]보다 작으므로 교환X {1, 2, 4, 5, 6}

 

배열 bubble의 버블 정렬 과정 - 2

 

첫번째 패스가 완료되면 가장 큰 요소가 맨 뒤로 이동하기 때문에

두번째 패스는 맨 끝의 요소를 제외하고 진행되고,

두번째 패스가 완료되면 두번째로 큰 요소가 맨 뒤에서 두번째로 이동하기 때문에

세번째 패스는 맨 끝의 두 요소를 제외하고 진행된다.

=> 패스가 한번씩 진행될 때 마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

 

메서드 swap() : a[idx1] 과 a[idx2] 를 교환

매개변수 : int[] a, int idx1, int idx2

 

메서드 bubbleSort() : 길이가 n인 배열 a를 버블 정렬

매개변수 : int[] a, int n

 

- 버블 정렬 (1) : 중간에 정렬이 완료된 상태가 되어도 끝까지 비교 수행

void swap(int[] a, int idx1, int idx2) {
	int t = a[idx1];
	a[idx1] = a[idx2];
	a[idx2] = t;
}

void bubbleSort(int[] a, int n) {
	for(int i = 0; i < n-1; i++) {
		for(int j = 0; j < n-i-1; j++) {
			if(a[j] > a[j+1]) {
				swap(a, j, j+1);
			}
		}
	}
}

 

- 버블 정렬 (2) : 중간에 정렬이 완료된 상태가 되면 더이상 비교하지 않고 종료

 

두번째 패스의 교환 횟수가 0이기 때문에 세번째 패스 없이 종료

   ( 한 패스에서 교환 횟수가 0이면 더 이상 정렬 할 요소가 없다는 뜻이기 때문에, 변수 exchg 를 추가하여 교환이 일어났는지 체크하고 교환 횟수가 0이면 종료 )

void swap(int[] a, int idx1, int idx2) {
	int t = a[idx1];
	a[idx1] = a[idx2];
	a[idx2] = t;
}

void bubbleSort(int[] a, int n) {
	for(int i = 0; i < n-1; i++) {
		int exchg = 0;
		for(int j = 0; j < n-i-1; j++) {
			if(a[j] > a[j+1]) {
				swap(a, j, j+1);
                exchg++;
			}
		}
		if (exchg == 0) {
			break;
		}
	}
}

 

- 버블 정렬 (3) : 한 패스 안에서 중간에 정렬이 더 이상 일어나지 않으면 다음 패스에서 정렬이 일어난 부분까지만 정렬

 

첫번째 패스에서 a[1] 이후에 정렬이 일어나지 않았기 때문에, 두번째 패스에서 a[0] 까지만 정렬 

   ( 한 패스 안에서 중간 a[j] 이후에 정렬이 더 이상 일어나지 않으면 a[j+1] 이후는 더 이상 정리할 요소가 없다는 뜻이기 때문에, 변수 last 를 추가하여 j를 저장, 다음 패스에서 j-1 까지만 정렬을 진행하도록 한다. )

void swap(int[] a, int idx1, int idx2) {
	int t = a[idx1];
	a[idx1] = a[idx2];
	a[idx2] = t;
}

void bubbleSort(int[] a, int n) {
	int k = n - 1;
	while(k > 0) {
		int last = 0;
		for(int j = 0; j < k; j++) {
			if(a[j] > a[j+1]) {
				swap(a, j, j+1);
				last = j;
			}
		}
		k = last;
	}
}

 

 

 

 

 버블 정렬 Bubble Sort :

최선 = 평균 = 최악 = O(N^2)

안정한 정렬