Java - Sorting algorithm (1)

1. Selection sort

public class SelectionSort {
	public static void main(String[] args) {
		int[] list = {29, 10, 14, 37, 13};
		printList(list, "Before");
			
		for(int i=list.length; i>1; i--) {
			int max = 0;
			for(int j=1; j<i; j++) {
				if(list[max]<list[j]) 
					max = j;
			}
			// ** exchange the maximum and last. 
			swap(max, list, i);
		}
		
		/// ** Print sorted array.
		printList(list, "After");
	}
	
	private static void printList(int[] list, String contents) {
		System.out.printf("%s = ", contents);
		for(int i=0; i<list.length; i++) {
			if(i==0)
				System.out.printf("{%d, ", list[i]);
			else if(i==list.length-1)
				System.out.printf("%d}\n", list[i]);
			else
				System.out.printf("%d, ", list[i]);
		}
	}
	
	private static void swap(int max, int[] list, int i) {
		int tmp = list[i-1];
		list[i-1] = list[max];
		list[max] = tmp;
	}
}

 

2. Bubble sort

public class BubbleSort {
	public static void main(String[] args) {
		int[] list = {29, 10, 14, 37, 13};
		printArray(list, "Before");
		
		for(int j=list.length-1; j>1; j--) {
			for(int i=0; i<j; i++) {
				if(list[i]>list[i+1]) {
					int tmp = list[i+1];
					list[i+1] = list[i];
					list[i] = tmp;
				}
			}
		}
		
		printArray(list, "After");
	}
	
	private static void printArray(int[] list, String contents) {
		System.out.printf("%s = ", contents);
		
		for(int i=0; i<list.length; i++) {
			if(i==0)
				System.out.printf("{%d, ", list[0]);
			else if(i==list.length-1)
				System.out.printf("%d}\n", list[list.length-1]);
			else
				System.out.printf("%d, ", list[i]);
		}
	}
}

 

3. Insertion sort

3.1. 직관적인 코드 (앞에서부터 비교)

public class InsertionSort {
	static int[] list = {15, 12, 13, 10, 14, 11};
	public static void main(String[] args) {
		printList("Before");
		insertion(1);
		printList("After");
	}
	
	private static void insertion(int index) {
		if(index==list.length) 
			return;
		else {
			int targetIndex = findLocation(index);
			int tmp = list[index];
			moveBack(targetIndex, index);
			list[targetIndex] = tmp;
			insertion(index+1);
		}
	}
	
	// *** Find the valid index.
	private static int findLocation(int index) {
		for(int i=0; i<index; i++)
			if(list[index]<list[i])
				return i;
		
		return index;
	}
	
	// *** Move back indexes.
	private static void moveBack(int start, int end) {
		for(int i = end-1; i>=start; i--)
			list[i+1] = list[i];
	}
	
	// *** Print the Array.
	private static void printList(String contents) {
		System.out.printf("%s = ", contents);
		
		for(int i=0; i<list.length; i++) {
			if(i==0)
				System.out.printf("{%d, ", list[0]);
			else if(i==list.length-1)
				System.out.printf("%d}\n", list[i]);
			else
				System.out.printf("%d, ", list[i]);
		}
	}
}

3.2. 간결한 코드 (뒤에서부터 비교)

public class InsertionSort {
	static int[] list = {15, 12, 13, 10, 14, 11};
	
	public static void main(String[] args) {
		printList("Before");
		insertion(1);
		printList("After");
	}
	
	private static void insertion(int index) {
		if(index==list.length)
			return;
		else {
			for(int i=index-1; i>=0; i--) {
				if(list[i+1]<list[i]) {
					int tmp = list[i+1];
					list[i+1] = list[i];
					list[i] = tmp;
				}
			}
			insertion(index+1);	
		}
	}
	
	// *** Print the array.
	private static void printList(String contents) {
		System.out.printf("%s sorting = ", contents);
		for(int i=0; i<list.length; i++) {
			if(i==0)
				System.out.printf("{%d, ", list[i]);
			else if(i==list.length-1)
				System.out.printf("%d}\n", list[i]);
			else
				System.out.printf("%d, ", list[i]);
		}
	}
}

• Selection sort나 Bubble sort는 최대, 최소, 평균 경우의 수가 모두 동일하다.
  ▶ T(n) = (n-1) + (n-2) + .... + 2 + 1 = n(n-1)/2 = O(n^2)
• 하지만, Insertion sort는 최악의 경우에 대해서만 selection sort와 bubble sort와 동일하며, 운이 좋을 경우 그보다 적은 시도를 통해 정렬할 수 있다.