[Algorithm] 혼자 결론 내린 정렬 알고리즘

버블

-> 이웃한 데이터끼리 비교하여 가장 큰 수를 계속 뒤로 보내는 정렬

-> 뒤에서부터 정렬이 이루어진다.

삽입

-> 정렬되지 않은 임의의 데이터를 정렬된 데이터와 비교하여 적절한 위치에 삽입하는 정렬

-> 앞에서부터 정렬이 이루어진다. 

-> 앞쪽에 정렬된 데이터와 비교를 한다 뒤에서 앞으로 가는 구조

선택

-> 정렬되지 않은 임의의 데이터 중 가장 작은 값을 비교하여 선택하여 가장 앞의 데이터와 위치를 바꿔주는 정렬

-> 앞쪽에서부터 정렬이 이루어진다

분할정복

-> 데이터를 분할정복 알고리즘으로 1/2로 쪼개고

-> 결합하는 과정에서 정렬을 진행한다.

public class SortTest {

	private static final int[] arr = new int[] {8,5,2,6,9,3,1,4,0,7};

	public static void main(String[] args) {
//		selectionSort(arr.clone());
//		insertionSort(arr.clone());
//		bubbleSort(arr.clone());
		print(arr);
		mergeSort(arr.clone());
	}
	
	
	public static void bubbleSort(int[] arr) {
		for(int i=0; i < arr.length - 1; i++){
			for(int j=1; j < arr.length - i; j++){
				if(arr[j-1] > arr[j]) swap(arr, j, j-1);
			}
			print(arr);
		}
	}
	
	public static void selectionSort(int[] arr) {
		int target = 0;
		for(int i=0; i<arr.length - 1;i++){
			target = i;
			for(int j=i+1; j <arr.length ; j++){
				if(arr[target] >= arr[j]) target = j;
			}
			swap(arr, i, target);
			print(arr);			
		}
	}
	
	public static void insertionSort(int[] arr) {
		for(int i=1; i<arr.length;i++){
			for(int j=0; j<i; j++){
				if(arr[j] > arr[i]) swap(arr, i, j);
			}
			print(arr);
		}
	}
		
	
	public static void mergeSort(int[] arr) {
		divide(arr, 0, arr.length - 1);
	}
	
	public static void merge(int[] arr, int s, int m, int e) {
		int[] temp = new int[arr.length];
		int i = s;

		int left = s;
		int right = m + 1;
		
		while(left <= m || right <= e) {
			if(arr[left] >= arr[right]) {
				temp[i] = arr[right];
				right++;
			} else {
				temp[i] = arr[left];
				left++;
			}
			i++;
		}
		
		for(int j=s;j<=m;j++){
			arr[j] = temp[j];
		}
		
		for(int j=m+1;j<=e;j++){
			arr[j] = temp[j];
		}
		
		print(arr);
	}
	
	public static void divide(int[] arr, int s, int e) {
		if(s < e){
			int middle = (e - s) / 2;
			System.out.println(s + "," + middle + "," + e);
			divide(arr, s, middle);		
			divide(arr, middle + 1, e);
			
			merge(arr, s, middle, e);
		}
	}

	
	
	public static void swap(int[] arr, int i, int j) {
		int tmp2= 0;
		tmp2 = arr[j];
		arr[j] = arr[i];
		arr[i] = tmp2;
	}
	
	public static void print(int[] arr) {
		for(int j=0; j <arr.length; j++){
			System.out.print(arr[j] + " ");
		}
		System.out.println("");
	}
	
}