'SelectionSort'에 해당되는 글 1건

  1. 2013.06.04 [C] 선택 정렬 (Selection Sort) 정의 / 코드
Programming/Algorithm2013. 6. 4. 12:52

 선택 정렬 (Selection Sort) 는 정렬이 되지 않은 데이터 영역에서 최소값을 찾아 데이터 영역의 가장 앞으로 이동하는 방식을 반복하여 전체 데이터 영역을 정렬하는 방법이다. 데이터가 많아질수록 많은 시간이 걸리고, 다른 정렬과 비교하여 장점이 없어, 추천하기 어려운 정렬 방법이다.

 위의 그림과 같은 단계를 통해서 정렬이 진행된다. 정렬이 되지 않은 데이터 영역에서 최소값을 찾아 가장 앞으로 이동한다. 이동한 값을 제외한 정렬이 되지 않은 데이터 영역에서 최소값을 찾아 가장 앞으로 이동한다. 이 방식을 반복한다. 이 방식은 항상 같은 비교 횟수((n-1) + (n-2) +  (n-3) ... + 2 + 1 = n * (n-1)/2 = n(n-1)/2)를 가지게 된다.

 

 선택 정렬을 다음과 같이 구현하였다.

 정렬이 되지 않은 데이터 영역의 가장 앞 위치를 iTemp_Processing 에 저장하고, iTemp_Compare 가 증가하며 값을 비교하여 가장 작은 값의 위치를 iTemp_MinPosition 저장한다. 마지막으로 iTemp_MinPosition 의 값을 iTemp_Processing 으로 이동한다. 이 방식을 반복한다. 정렬할 때에 사용하는 Swap 함수, 이 정렬 사용하는 예제는 이전 글(링크 : [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선)에서 확인할 수 있다.

Posted by 개발자테오