SortingTest.java

public class SortingTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] alist = {54,26,93,17,77,31,44,55,20};
		
		printArray(alist);
		
		//selectionSort(alist);
		//insertionSort(alist);
		mergeSort(alist);
		printArray(alist);
	}
	
	private static void selectionSort(int[] arr){ // O(N^2)
		
		int numArray = arr.length;
		int minIndex;
		
		
		
		for (int i = 0; i < numArray; i++ ){ // O(N)
			int min = arr[i];
			minIndex = i;
			
			for (int j = i+1; j<numArray; j++){ // O(N-1)
				if (arr[j] < min){
					min = arr[j];
					
					System.out.println(i + " 번째 min: " + min);
					minIndex = j;
				}
			}
			
			arr[minIndex] = arr[i];
			arr[i] = min;
			// printArray(arr);
		}
		
	}
	
	private static void insertionSort(int[] arr){ // O(N^2)
		
		int numArray = arr.length;
		int temp;
		
		for (int i = 1; i < numArray; i++) { // 0 부터 시작하면 arr[0] 이전의 원소가 없으므로 1부터 시작
			temp = arr[i];
			for (int j = i-1; j >= 0 && arr[j] > temp ; j-- ){ // arr[j] is the element to be compared with temp
															   // loop from arr[i-1] to arr[0] 
															   // stop when arr[j] < temp
											 // arr[j]   temp    arr[j+1]
											 //   54      26       26
			//	if (arr[j] > temp){			 //   54   >  26       26
					arr[j+1] = arr[j];		 //   54	  26	   54	
					arr[j] = temp;			 //   26      26	   54
			//	}
			}
			
			// printArray(arr);  // use this for visualizing how it is sorted
		}
	}
	
	private static void mergeSort(int[] arr){
		mergeSortHelper(arr, 0, arr.length-1);
	}
	
	private static void mergeSortHelper(int [] arr, int low, int high){
		// Step 1 : find the middle of the array
		// base case
		if (low == high) return;
		
		// recursive case
		int mid = ( low + high ) / 2;
				
		// Step 2 and 3: Sort the 2 halves of arr
		mergeSortHelper(arr, low, mid);
		mergeSortHelper(arr, mid+1, high);
		
		// Step 4: Merge sorted halves into an auxiliary array
		int[] tmp = new int[high-low+1];
		int left = low;
		int right = mid+1;
		int pos = 0;
		
	    while ((left <= mid) && (right <= high)) {
	        // choose the smaller of the two values "pointed to" by left, right
	        // copy that value into tmp[pos]
	        // increment either left or right as appropriate
	        // increment pos
	            if (arr[left] < arr[right]){
	            	tmp[pos] = arr[left];
	            	pos++; left++;
	            }
	            else {
	            	tmp[pos] = arr[right];
	            	pos++; right++;
	            }
	        }
	    
	    // when one of the two sorted halves has "run out" of values, but
	    // there are still some in the other half, copy all the remaining 
	    // values to tmp
	    // Note: only 1 of the next 2 loops will actually execute
	    while (left <= mid) { 
	    	tmp[pos] = arr[left];
	    	pos++; left++;
	    }
	    while (right <= high) {
	    	tmp[pos] = arr[right];
	    	pos++; right++;
	    }
		
	    
	 // all values are in tmp; copy them back into arr
	    System.arraycopy(tmp, 0, arr, low, tmp.length);
	}
	
	private static void printArray(int[] arr){
		for (int i : arr){
			System.out.print(i + ", ");
		}
		System.out.println();
	}

}