[자료구조/sort] 선택정렬

첫번째 자리에 나머지 것들(1~6번쨰)중 최소값 넣는다.

두번째 자리에 나머지 것들(2~6번쨰)중 최소값 넣는다.

......

다섯번째 자리에 5~6번째 중 최소를 넣는다.

---> 즉 나머지것들 중에서 제일 작은 혹은 제일 큰 것을 선택해서 정해진 자리에 넣는것이 선택정렬

for(int i=0; i<n-1; i++)

{

int k=i;

for(int j=i; j<n; j++)
{

if(arr[j]<arr[k]) //k를 제일 첫번째수의 인덱스로 정해놓고 검색하면서 더작은게 나오면 k를 갱신

k=j;

}

//제일 작은 수 검색 했으면 arr[i]와 arr[k]를 교환해줌.

}

비교횟수 빅오 O(N2) 

데이터 이동 빅오 O(N)

선택정렬과 버블정렬 데이터 이동 횟수 비교

최악의 경우 선택정렬 < 버블정렬  (선택정렬이 더 적게 데이터를 이동한다.)

->선택정렬은 최악이든 최선이든 데이터 이동은 O(N)임.

최선의 경우 버블정렬 < 선택정렬 (버블정렬이 더 적게 데이터를 이동한다.)

->버블정렬은 최선의 경우 데이터이동횟수 0

둘다 비교횟수는 차이가 없음!! 단지 데이터 이동 횟수에서 상황에 따라 차이가 날뿐이다.