[정렬] 버블, 선택, 삽입 정렬

1. 버블 정렬

- 인근 원소를 하나씩 비교하여 최대값 혹은 최소값이 맨 끝으로 이동

- 거품이 올라오는 것 처럼, 하나 씩 정렬 됨.

- 처음 전체 원소를 비교하는데 (n-1) 번 비교연산, 두번째는 (n-2), 세번째, (n-3)...

- (n-1)+(n-2)+(n-3)+...+2+1 = n(n-1)/2

- O(n^2)

public class BubbleSort {
	public static void main(String[] args) {
		int[] data = { 12, 10, 8, 6, 3};
		
		for (int i = 0; i < data.length - 1; i++) {
			for (int k = 0; k < data.length - 1 - i; k++) {
				if (data[k] > data[k+1]) {
					int temp = data[k]; 
					data[k] = data[k+1];
					data[k+1] = temp;
				}
			}
		}
		
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] +", ");    // 3, 6, 8, 10, 12,	
		}
	}
}

2. 선택 정렬

- 일단 첫번째부터 끝까지 비교하며 가장 작은게 1번째 이동, 2번째부터 끝까지 비교하여 가장 작은게 2번째로 이동, .. (n-1)번 반복

- 최선일 경우 비교회수 : n-1

- 최악일 경우 비교회수 : n(n-1)/2

- O(n^2)

public class SelectionSort{
	public static void main(String[] args) {
		int[] data = {12, 10, 8, 6, 3};
		
		for (int i = 0; i < data.length - 1; i++) {
			for (int k = i; k < data.length - 1; k++) {
				if (data[i] > data[k+1]) {
					int temp = data[i]; 
					data[i] = data[k+1];
					data[k+1] = temp;
				}				
			}
		}
		
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] +", ");			
		}
	}
}