Simple Sort

강의 사이트

• http://www.kocw.net/home/search/kemView.do?kemId=1148815

정렬

• 아래 모두 실행시간은 O(n^2)

Bubble sort

public class Bubble {
	public static void main(String[] args) {
		int[] sort = new int[] {29, 10, 14, 37, 13};
		bubbleSort(sort);
		printArray(sort);
	}

	private static void printArray(int[] sort) {
		for(int i = 0; i < sort.length; i++) {
			System.out.print(sort[i] + " ");
		}
		
		System.out.println();
	}
	
	private static void bubbleSort(int[] sort) {
		
		for(int i = 0; i < sort.length ; i++) {
			for(int j = 0; j < sort.length-i-1; j++) {
				if(sort[j] > sort[j+1]) {
					int temp = sort[j];
					sort[j] = sort[j+1];
					sort[j+1] = temp;
				}
			}
		}
	}
}

Insertion sort

• 뒤에서부터 비교를 해야 shift하기 효율적이다.
• 이것도 최악은 select와 bubble과 같이 O(n^2)이지만 평균적으로는 N(N-1) /2 의 시간복잡도를 가진다.
• 따라서 평균 복잡도는 이것이 낫다

public class Insertion {
	public static void main(String[] args) {
		int[] sort = new int[] {29, 10, 14, 37, 13};
		insertSort(sort);
		printArray(sort);
	}

	private static void printArray(int[] sort) {
		for(int i = 0; i < sort.length; i++) {
			System.out.print(sort[i] + " ");
		}
		
		System.out.println();
	}
	
	private static void insertSort(int[] sort) {
		for(int i = 1; i < sort.length; i++) {
			int key = sort[i];
			int j = 0;
			
			for(j = i-1; j >= 0 && key < sort[j]; j--) {
				sort[j+1] = sort[j];
			}
			
			sort[j+1] = key;
		}
	}
}

Selection sort

public class SelectSort {
	
	public static void main(String[] args) {
		int[] sort = new int[] {29, 10, 14, 37, 13};
		selectSort(sort);
		printArray(sort);
	}

	private static void printArray(int[] sort) {
		for(int i = 0; i < sort.length; i++) {
			System.out.print(sort[i] + " ");
		}
		
		System.out.println();
	}

	private static void selectSort(int[] sort) {
		
		for(int i = sort.length-1; i >= 0 ; i--) {
			
			for(int j = i-1; j >=0; j--) {
				if(sort[i] < sort[j]) {
					
					int temp = sort[i];
					sort[i] = sort[j];
					sort[j] = temp;
				}
			}
		}
	}
}