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

버블정렬(Bubble Sort)

- 제자리 정렬(In-placed sorting) 알고리즘

- 인접한 두 개의 데이터의 대소값을 비교해 정렬하는 방식

- 1 cycle 이 후, 가장 큰 값이 맨 뒤에 위치

- 구현이 간단

- 시간 복잡도 : O(n^2)

 

 

선택정렬(Selection Sort) 과정

n개의 데이터가 주어졌을 때,

 

 

첫번째 인덱스부터 시작해 인접한 두 개의 값을 비교해 값을 비교해가며 정렬을 한다.

한 사이클을 다 돌게 되면 가장 큰 값이 맨 뒤에 위치하게 된다.

 

두번째 사이클도 첫번째 사이클과 마찬가지로

첫번째 인덱스부터 시작해 인접한 두 값을 비교해 정렬을 한다.

단, 맨 뒤의 값은 이전 사이클에서 이미 가장 큰 값이 위치하기 때문에 n - 1 번째 인덱스까지 정렬을 한다.

즉, i번째 사이클에서는 n - i 번째 인덱스까지만 정렬을 해주면 된다. 

 

같은 방식으로 n번의 사이클을 돌면 정렬된 상태의 데이터를 얻을 수 있다.

 

 

소스코드

package algorithm;

public class bubbleSort {
	public static void main(String[] args) {
		int[] a = {7, 8, 1, 9, 4, 6};
		
		for(int i = 1; i < a.length; i++) {
			for(int j = 1; j < a.length - i; j++) {
				if(a[j - 1] > a[j]) {
					int tmp = a[j - 1];
					a[j - 1] = a[j];
					a[j] = tmp;
				}
			}
		}
		
		for(int i = 0; i < a.length; i++) {
			System.out.printf("%d ",a[i]);
		}
	}
}