선택정렬

선택정렬은 말그대로 어떤 기준에 맞는 것을 선택하여 바꾸는 알고리즘이다. 

13번까지 array를 돌면서 가장 작은 값을 min에 넣어주고 그 가장 작은 값이 있는 위치를 index에 넣어준다. 

그리고 현재 i=0이기 때문에 해당 위치에 있는 값을 temp에 넣어주고 

0번위치에 가장 작은 값이 있던 위치의 값을 넣어준다. 

그리고 그 처음 i=0의 위치에 있던 값을 index에 넣어 위치를 바꿔주는 알고리즘이다. 

 

이 선택 정렬의 시간 복잡도는 O(N^2)이다. 

 

1 ,2 3, 4, 5, 6, 7, 8, 9, 10 이렇게 10개의 숫자 배열이 있다면 

서로 크기를 비교하기 위해 처음에 10번, 가장 작은 값을 찾았다면 그거 빼고 9번, 8번....1번 

총 10+9+8+7+...+2+1= 55번 비교를 한다. 

이것은 10 * (10+1)/2 로 표현할 수 있고 

이것은 N * (N+1)/2 로 표현할 수 있다. 

하지만 N이 무지하게 크다면 /2를 하는 것은 의미가 없다. 

따라서 N^2이 남게 되고 이것을 빅오 표기법으로 나타내면 

O(N^2)로 표기한다. 

 

즉 만약 N이 1000개라면 1000*1000번으로 매우 오래걸린다. 

따라서 효율적인 알고리즘으로 하기는 힘들다.