빅 오 표기법 3. 선택 정렬

인덱스 0부터 패스스루하는데 각 시점의 최솟값을 구해 그 최소값과 같은 원소값고 시작 인덱스 원소값만 바꾼다.

 

최솟값(2)	최솟값(2)	최솟값(1)	최솟값(1)
2	6	1	4

 

1

6

2

4

 

이후 인덱스 0은 값이 정해졌으니 인덱스 1부터 다시 반복한다.

 

선택 정렬일때는 (N-1) + (N-2)... + 1 = 번의 비교가 나타난다. 비교단계는 버블정렬과 같다.

 

하지만, 교환은 패스스루 한번당 한번만 나타난다. 즉, N - 1 의 교환단계가 발생한다.

 

 

N개의 원소	버블 정렬에서 최대 단계 수	선택 정렬에서 최대 단계 수
5	20	14(10 + 4)
10	90	54(45 + 9)
20	380	199(180 + 19)
40	1560	819(780 + 39)
80	6320	3239(3160 + 79)

 

선택정렬은 약 N^2/2 단계가 필요하다. 즉, 버블정렬 N^2보다 효율적이다. (선택정렬이 2배 더 효율적)

그러나 빅 오 표기법은 상수를 무시한다. 그래서 버블정렬이나 선택정렬이나 N^2 게 표현한다.

function selectionSort(array) {
	for(var i = 0 ; i < array.length ; i++) {
    	var lowestNumberIndex = i;
        for(var j = i + 1 ; j < array.length ; j++) {
        	if(array[j] < array[lowestNumberIndex]) {
            	lowestNumberIndex = j;
            }
        }
        if(lowestNumberIndex != i) {
        	var temp = array[i];
            array[i] = array[lowestNumberIndex];
            array[lowestNumberIndex] = temp;
        }
    }
    return array;
}