[Algorithm] 정렬 - Selection Sort (선택 정렬)

Selection Sort

• 처음 index부터 마지막 index까지의 이동하며 최대값을 찾은 후 저장하는 방식
• k-index에 들어갈 원소를 찾기위해서 k-1번 최대값을 찾는 비교를 해야하므로 O(n^2)이다.

• 

  https://en.wikipedia.org/wiki/Selection_sort

동작

Step1

Step2

Step3

Step4

Step5

Step6

 

 

 

 

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
	
	public void selectionSort(int[] arr) {
    	for(int i = arr.length-1; i >= 0; i--) {
        	int maxIndex = i;
            int j;
            for(j = 0; j < i; j++) {
            	if(arr[j] > arr[maxIndex]) {
                	maxIndex = j;
                }
            }
            swap(arr, i, maxIndex);
        }
    }
    
    
}