버블 정렬

 

1. 버블 정렬

 

버블 정렬은 다음과 같이 진행된다. (오름차순 기준)

 

1. 맨 앞 숫자(a) 부터 비교를 시작한다.

 

2. 바로 뒤의 숫자(b) 와 비교해서 뒤의 숫자가 더 작으면 자리를 바꿔준다.

 

즉, a b 순서였는데

b < a  이면 b a 로 자리를 바꿔준다.

 

3. 그 다음 숫자와 비교하면서 위와 같은 과정을 반복한다.

 

4. 맨 끝까지 비교가 끝나면 다시 맨 앞 숫자를 뒤의 숫자와 비교한다.

 

 

시간 복잡도

최선의 경우 : O(N)

평균 : O(N*N)

 

단점 : 다른 정렬 알고리즘에 비해 교환과정이 많아서 시간 소비가 크다.

 

 

2. 그림으로 설명

다음과 같은 상황이라고 하자.

 

 

단계 1

 

 

 

맨 앞에 있는 값은 1이다.

바로 뒤의 5와 비교한다.

5가 더 크므로 둘의 자리를 그대로 둔다.

 

그 다음 5와 3을 비교해서 5가 더 크므로 자리를 바꾼다.

 

 

 

5보다 4가 작으므로 자리를 바꿔준다.

 

 

 

5보다 2가 작으므로 자리를 바꿔준다.

 

그럼 이제 끝이났다.

맨 마지막에 위치한 5는 이제 확정이 되었다.

 

 

 

단계 2

 

또 다시 맨 앞에 있는 값과 뒤의 값을 비교한다.

1과 비교해서 3이 크기 때문에, 그대로 두면 된다.

 

 

 

역시 그대로 두면 된다.

 

자리를 바꿔준다.

 

5는 이미 단계 1에서 확정되었기 때문에 4,5를 비교할 필요 없다.

4도 확정된다.

 

단계 3

 

 

단계 4

 

결론

 

단계를 진행할 때마다 뒤에서 한 개씩 정렬되기 때문에 

비교하는 횟수가 점점 줄어들게 된다.

 

 

3. 최종 코드 

 

1) 시간 복잡도 : O(N*N) 

 

import java.io.IOException;
import java.util.Arrays;


public class Main {
	
	public static void main(String[] args) throws IOException {
		
		int a[] = {1,5,3,4,2};
		
		int size = 5;
		
		for(int i =1; i< size; i++) {
			
			for(int j =0; j<size - i; j++) {
				
				if(a[j] > a[j+1]) {
					
					int value = a[j];
					a[j] = a[j+1];
					a[j+1] = value;
					
				
				}
			}
		}
		
		System.out.println(Arrays.toString(a));
	}
}

 

 

2) 시간 복잡도 : O(N) - 최선의 경우 , O(N*N)  - 최악의 경우 

 

 

위에서 최선의 경우에는 시간복잡도가 O(N) 이라고 했다.

최선의 경우는 1 2 3 4 5 가 있겠다.

이미 정렬이 되어 있는 상태이다.

 

그런데 위의 코드로는 최선의 경우에도 O(N*N) 이 된다.

 각 단계마다 앞에 있는 숫자가 큰 지 뒤에 있는 숫자가 큰지 비교해야 되기 때문이다.

 

그래서 다음과 같은 코드를 만들어서,

각 단계에서 숫자들의 대소 비교한 뒤, 

그 단계에 모두 정렬되어 있다는 것이 판단되면

정렬을 종료하도록 한다.

 

즉 아래의 코드는

boolean 형 변수 check 를 사용한다.

그리고 처음에 check = false 로 초기화한다.

 

단계 1은

맨 처음 숫자부터 마지막까지 앞, 뒤 숫자의 대소를 비교한다.

그런데 만약

입력값이 1 2 3 4 5 라면 

정렬이 된 상태이므로 

앞 뒤 위치가 바뀌는 일이 없을 것이다.

 

그러면 check = false로 변함없게 한다.

 

즉, 단계 1을 진행한 뒤 여전히 check = false 라면

단계 2로 넘어가는게 아니라

반복문을 종료해서 정렬을 끝내는 것이다.

즉 이렇게 되면 시간 복잡도는 O(N) 을 만족한다.

 

하지만 입력값이

5 4 3 2 1 이라면,

정렬이 필요하고,

단계 1에서 숫자들의 위치를 바꿔줘야 한다.

 

이렇게 바꾸는 상황이 생기면 check = true 로 바꿔서,

반복문이 끝나지 않고 정렬을 계속 진행되도록 하면 된다.

이 경우도 물론 최악의 경우는 O(N*N) 이 발생할 수 있다.

 

 

 

 

import java.io.IOException;
import java.util.Arrays;


public class Main {
	
	public static void main(String[] args) throws IOException {
		
		int a[] = {1,2,3,4,5};
		
		int size = 5;
		
		for(int i =1; i< size; i++) {
			
			boolean check = false;
			
			for(int j =0; j<size - i; j++) {
				
				if(a[j] > a[j+1]) {
					
					int value = a[j];
					a[j] = a[j+1];
					a[j+1] = value;
					
					check = true;
				}
			}
			
			
			
			if(check==false) {
				break;
			}
		}
		
		System.out.println(Arrays.toString(a));
	}
}

 

 

 

 

참고 블로그 : 

 

https://st-lab.tistory.com/195