Selection Sort (선택 정렬)

Selection Sort (선택 정렬)

• 전체 자료 중, 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식

• 입력 배열 외 추가 메모리를 요구하지 않음.

• 장점 : 자료 이동 횟수가 사전에 정해진다.

• 단점 : 값이 같은 경우에도 위치가 변경되므로 안정성을 만족하지 않는다. -> Code에서 극복하는 부분 참조

• 시간복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

• 동작 순서 (최소 선택 정렬을 예시로 함.)

  1. 첫 번째 인덱스부터 마지막까지 크기를 비교하여 제일 작은 값을 찾는다.
  2. 현재 인덱스와 제일 작은 값의 위치를 바꾼다.
  3. 두 번째 인덱스부터 위 정렬을 반복한다.
  4. 반복.

• Code

  #include <stdio.h>                                      // 헤더파일 선언
  #define ARRAY_SIZE 10                                   // ARRAY SIZE 10으로 정의
  // Logic 부---------------------------------------------
  void selection_sort(int array[], int n)                 // 선택 정렬 함수 및 인수 선언
  {
      int least, temp;                                    // 최소값과 위치변경을 위한 변수 선언
      for(int i=0;i<n-1;i++)                              // n-1 회 반복
      {
          least = i;                                      // 최소값에 i 대입
          for(int j=i+1;j<n;j++)                          // i+1 부터 n 까지 반복 
          {
              if(array[least]>array[j])                   // array[least]가 array[j]보다 크면
                  least = j;                              // least에 j 대입
          }
          // if(array[i] != array[least])                 // -> 값이 같은 경우 위치 변경하지 않도록 조건 설정
          temp = array[i];
          array[i] = array[least];
          array[least] = temp;                            // i번째 인덱스와 최소값 인덱스 변경
      }
  }
  // Main 부----------------------------------------------
  void main()
  {
      int Arr[ARRAY_SIZE] = {3,6,8,4,0,7,5,1,2,9};        // Arr 선언 및 임의의 값 대입
      selection_sort(Arr, ARRAY_SIZE);                    // 선택 정렬 함수 실행
      for(int i=0;i<ARRAY_SIZE;i++)                       // ARRAY_SIZE 만큼 반복
      {
          printf("%d\t",Arr[i]);                          // i번째 Array 값 출력
      }
  }

  Output : 0    1    2    3    4    5    6    7    8    9