[내가 몰라서 정리하는 알고리즘] 2. 버블정렬

버블정렬

---

(본 공부는 전부 자바를 기반으로 합니다.)

 

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다.

아주 간단하고 직관적이지만 가장 효율성이 떨어지는 알고리즘이다.

0부터 시작하여 왼쪽의 값이 오른쪽 값보다 크다면 두 수의 자리를 바꿔준다.

버블정렬은 한 턴이 끝날때마다 가장 큰 값이 맨 뒤로 이동 된다.

그 후에 맨 뒤의 인덱스를 제외하고 맨 처음부터 맨 뒤의 앞 인덱스까지만 비교하여 정렬을 수행한다.

이렇게 정렬을 반복하면 반복할 때마다 집합의 크기가 1씩 줄어든다.

 

 

 

(선택정렬과 같은 예제를 가지고 왔다.)

Q) 1 10 5 8 7 6 4 3 2 9

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

 

 

A)

1턴 : [0]부터 [9]까지 왼쪽의 값과 오른쪽의 값을 비교해가면서 바꿔준다.

1턴 - 1 ) 1 10 5 8 7 6 4 3 2 9

1턴 - 2 ) 1 5 10 8 7 6 4 3 2 9

1턴 - 3 ) 1 5 8 10 7 6 4 3 2 9

1턴 - 4 ) 1 5 8 7 10 6 4 3 2 9

1턴 - 5 ) 1 5 8 7 6 10 4 3 2 9

1턴 - 6 ) 1 5 8 7 6 4 10 3 2 9

1턴 - 7 ) 1 5 8 7 6 4 3 10 2 9

1턴 - 8 ) 1 5 8 7 6 4 3 2 10 9

1턴 - 9 ) 1 5 8 7 6 4 3 2 9 10

 

턴을 한 번 마무리 짓게 되면 위와 같이 가장 큰 10이 맨 뒤로 이동했음을 알 수 있다.

이런 식으로 턴을 반복한다 !

.

.

.

반복하면 총 결과는 1 2 3 4 5 6 7 8 9 10 이 된다.

 

 

 

1턴에서는 10번 비교연산을 수행하고, 2턴에서는 맨 뒤 인덱스를 제외하여 9번의 비교 연산을 수행한다.

3턴에서는 맨 뒤 인덱스와 그 앞 인덱스를 제외하여 8번의 비교 연산을 수행하여

이렇게 반복하여 연산을 수행하게 되면 총 연산 횟수는 다음과 같다.

 

10 + 9 + 8 + 7 + ... + 1

 

총 비교 연산의 횟수는 선택정렬과 같은 결과가 나온다.

 

 

N * (N+1) / 2

 

 

그래서 결과적으로 버블정렬의 시간복잡도 또한 선택정렬과 같은 O(N^2) 을 갖는다는 것을 알 수 있다.

 

버블정렬의 시간복잡도는 선택정렬의 시간복잡도와 같지만 선택정렬보다는 속도가 느리다.

선택정렬은 가장 작은 값을 선택하여 맨 앞으로 보내주는 방법으로 수행되지만 버블정렬은 계속해서 옆의 값과 비교하여 위치를 바꿔주는 방법으로 수행되기 때문에 매번 교체를 해줘야한다.

그렇기에 선택정렬보다 훨씬 비효율적인 알고리즘이라고 할 수 있다 ..!

 

 

 

public class BubbleSort {
	public static void main(String args[]) {
		int i, j, temp;
		//int min; //최소값을 저장할 필요가 없다.
		int array[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
		for(i=0;i<10;i++) {
			for(j=0;j<9-i;j++) {
				//버블 정렬은 한 턴이 끝날때마다 맨 뒤에 있는 값은 비교하지 않기 때문에 범위는 9-i로 해준다.
				if(array[j] > array[j+1]) { //왼쪽의 값이 오른쪽 값보다 크다면
					temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
					//두 수의 자리를 바꿔준다.
				}
			}
		}
		
		for(i=0;i<10;i++) {
			System.out.print(array[i]+" ");
		}
	}
}

 

---

 

버블정렬 또한 쉬운 문제에 적용을 해보자!

문제 출처 : JUNGOL (정보 올림피아드 & 알고리즘) http://www.jungol.co.kr/ 1157 : 버블정렬 문제

 

 

import java.util.*;

public class prac_1157 {
	public static void main(String args[]) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int array[] = new int[n];
		int i,j,temp;
		for(i=0;i<n;i++) {
			array[i] = s.nextInt();
		}
		for(i=0;i<n;i++) {
			for(j=1;j<n-i;j++) {
				if(array[j-1] > array[j]) {
					temp = array[j-1];
					array[j-1] = array[j];
					array[j] = temp;
				}
			}
			for(int x=0;x<n;x++) {
				if(i != n-1) {
					System.out.print(array[x]+" ");
				}
			}
			System.out.println();
		}
	}
}

 

참고로 덧붙이자면 위의 예제를 활용하여 코드를 짰을 때에는 0부터 시작하여 9-i 까지만 for문을 실행하여

왼쪽(j)의 값을 기준으로 오른쪽(j+1)의 있는 값을 비교하는 식으로 밑의 문제를 풀었을 때

배열의 인덱스를 초과하는 문제가 발생한다.

그렇기 때문에 문제를 풀 때에는 1부터 시작하여 오른쪽(j)의 값을 기준으로

왼쪽의 값(j-1)을 설정해주어야 문제가 풀린다.

 

 

더 자세한 코드는 https://github.com/suhyeong (Simple Mars) 을 참고하세요.