[알고리즘] 선택정렬

SelectionSort

1) swapElement
배열에 있는 두 요소의 값을 바꿈
요소를 읽고 쓰는 것 : 상수 시간 연산

// 배열에서 i와 j 위치에 있는 값 바꿈
public static void swapElement(int[] array, int i, int j){
	int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

2) indexLowest

start의 위치에서부터 배열에 있는 가장 작은 요소의 인덱스 찾음
비교횟수 : n - start (n: 요소 개수)

public static int indexLowest(int[] array, int start){
    int idx = start;
	for(int i = start; i < array.length; i++)
        if(array[i] < array[idx])
            idx = i;
	return idx;
}

3) selectionSort

배열 정렬
0 ~ n-1까지 반복하므로, n번 반복 실행

public static void selectionSort(int[] array){
	int idx = 0;
    for(int i = 0; i < array.length; i++){
    	idx = indexLowest(array, i);
        swapElement(array, i, idx);
	}
}

총 비교횟수

n + n-1 + n-2 + ... + 1 = n(n+1)/2 => n^2에 비례 O(n^2)