[자료구조] 선택 정렬 ( Selection Sort )...

[자료구조] 선택 정렬...
선택 정렬(selection sort)은 전체 원소들 중에서 기준 위치에 맞는 원소를 선택

하여 자리를 교환하는 방식으로 정렬한다. 전체 원소 중에서 가장 작은 원소를

찾아서 선택하고 첫번째 원소와 자리를 교환한다. 그 다음 두번 째로 작은 원소

를 찾아서 두번째 원소와 자리를 교환하고, 그 다음에는 세 번째로 작은 원소를
찾아서 세 번째 원소와 자리를 교환한다. 이 과정을 반복하면서 정렬을 완성한다.
 
정확한 자료의 값 이동은 맨 아래의 동영상을 참고하면 된다.

(유투브에서 검색하면 바로 나오는 거라서 일단 퍼왓는데 문제가 된다면 삭제

하겠다.)

간단한 선택정렬 함수이다.

void selectionSort(int a[], int n )
{
   int i, j, min, temp ;
   for( i =0 ; i < n-1; ++i )
   {
      min = i ;
      for ( j= i+1; j < n; ++j )
      {
         if ( a[j] < a[min] ) min = j ;
      }
      temp = a [i] ;
      a [i] = a [min] ;
      a[min] = temp ;
   }
}

n 개의 원소에 대한 선택 정렬은 n개의 메모리를 사용한다. 선택 정렬에서의 비

교 횟수를 구해보면, 1단계에서는 첫 번째 원소를 기준으로 n개의 원소를 비교

하고, 2단계에서는 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소를

비교하고, 3단계에서는 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원

소를 비교한다. 이러한 방법으로 i단계에서는 i번째 원소를 기준으로 n-i개의 원

소를 비교하게 되므로 전체 비교 횟수는 n(n-1)/2 와 같다. 

선택정렬에서는 어떤 경우에서나 비교 횟수가 같으므로 시간 복잡도는 O(n²)이
된다.