티스토리 뷰

자료구조

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

심재철 2017. 8. 16. 22:24

첫번째 자리에 나머지 것들(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


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

댓글
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함