[오락실]선택정렬

1. 선택정렬(Selection Sort)이란?

-. 실제 프로그래밍에서 많이 사용되는 간단한 정렬방법으로 오름차순을 기준으로 한다면,

    최소값을 찾아 왼쪽으로 이동시키는데 배열크기만큼 반복하여 정렬하는 방법이다.

-. 가장 작은 값을 찾아서 첫번째 위치에 있는 값과 교환하고, 두번째로 작은 값을 찾아 두번째

    위치에 있는 값과 교환하는 방법으로 이러한 방법을 반복한다.

2. 버블정렬을 이용하여 오름차순으로 정렬하는 그림

3. 선택정렬의 비교회수

-. 최선일 경우의 비교회수 공식 : N - 1

-. 최악일 경우의 비교회수 공식 : N(N – 1)/2

-. 위의 그림을 보시면 아시겠지만 제일 처음에는 (N – 1)번을 비교하고,

   그 다음에는 (N – 2)번 만큼 비교하고, 그 다음은 (N – 3)번을 비교하면서 비교회수가 1이 될

   때까지 이 작업을 반복할 것이다.

-. 비교회수는 (N – 1) + (N – 2) + (N – 3) …… + 1 이 될 것이다.

   최대 (N – 1)번을 수행할 것이며, 각 패스가 수행할 때마다

   수학식으로 표현하면    이므로 공식은 N(N – 1)/2 이런 공식이 성립된다.

-. 5개의 값을 오름차순으로 선택정렬을 하면...

   공식에 의해서 5(5 – 1)/2 = 10 가 성립된다.

   즉, 총 10번의 비교를 통해서 오름차순으로 정렬된 값을 볼 수 있다.

 

4. 선택정렬의 연산시간

   -. 연산시간 공식 : O(n²)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

-. 수학식으로 표현하면 아래와 같다.

     = n(n – 1) – (n – 1)/2 = n(n - 1)/2 이므로 Worst Case는 n(n – 1)/2 이다.

   그래서 연산시간은 O(n²)가 되는 것이다.

  

5. 선택정렬의 장점

-. 데이터의 양이 적을 때 아주 좋은 성능을 나타낸다.

-. 작은 값을 선택하기 위해서 비교는 여러 번 하지만 교환횟수가 작다

 

6. 선택정렬의 단점

-. 가장 작은 값과 현재값을 교환하는 방식이라 현재값이 뒤쪽의 어디로 갈지 알 수 없으므로

    안전성이 없다.

-. 100개 이상의 자료에 대해서는 속도가 급격히 떨어져서 적절히 사용되기가 힘들다.

 

7. 선택정렬을 이용해서 작성한 예제

int SelectonSort(int *arr, int arrSize)
{
  int cmpCnt = 0;
  int i, j;
  int temp;
  int minIndex;
  
  for( i = 0; i < arrSize - 1; ++i )
  {
    minIndex = i;
    for( j = i + 1; j < arrSize; ++j )
    {
      ++cmpCnt;
      if( arr[minIndex] > arr[j] )
      {
        minIndex = j;
      }
    }
    temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }

  return cmpCnt;
}