선택정렬(selection sort)

Goal

      - Selection Sort 에 대해 설명할 수 있다.

      - Selection Sort 과정에 대해 설명할 수 있다.

      - Selection Sort를 구현할 수 있다.

      - Selection Sort의 시간 복잡도를 계산 할 수 있다.

---

1. Selection Sort Summary

   

     '가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘'

     '가장 원시적이고 기초적인 방법 중 하나'

---

2. Selection Sort Processing

 

           주어진 배열 중에 최소값을 찾는다.

                                  ↓

           그 값을 맨 앞에 위치한 값과 교체한다.

                                  ↓

           맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

---

3. Selection Sort 구현

#include <stdio.h>

int main(void)
{
                 int i, j, min, index, temp, n;                 // i행, j행, 최소값, 배열 인댁스값, 임시저장temp, 정수 n개 변수 선언 
                 int array[n];                                         // int형 정수 10개 담을 수 있는 정수 배열 선언  
                 n = sizeof(array)/sizeof(int);               // 정수 값 중복 최소화

                 printf(" 정수 n을 입력하세요 :");
                 scanf("%d", &n);

                 //배열 에 정수 입력  
                 for( i = 0; i < n; i++)
                 {
                             printf("array[%d] == >", i);
                             scanf("%d", &array[i]);
                  }

                 //선택정렬(Selection Sort)
                 for(i = 0 ; i < n; i++)                                // i는 0부터 n개의 정수 만큼 반복 (행) 
                 {
                             min = 9999;                               // 최소값 초기화 
                             for(j = i; j < n; j++)  // j는 0부터 n 개의 정수 만큼 반복 (열) 
                             {
                                             if(min > array[j])          // min이 array[첫번째] 보다 무조건 크기때문에 첫번째 값이 들어감 
                                             {
                                                           min = array[j];
                                                           index = j; 
                                              }
                              }
                                   temp = array[i];                       //변수 스와핑  
                                   array[i] = array[index];
                                   array[index] = temp;
                 }
                 //정렬 후 출력 
                 for(i = 0 ; i < n; i++)
                 {
                            printf(" %d ", array[i]);
                 } 
                return 0;
 }

---

4. Selection Sort 시간 복잡도

 

                데이터의 개수가 n개라고 했을때

                   - 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1

                   - 두 번째 회전에서의 비교횟수 : 2 ~ (n-2) => n-2

                      ....

                   - (n-1) + (n-2) ..... + 2 + 1 => N * (N-1) /2 (등차수열) 

                   => 컴퓨터에서는 가장 큰 차수인 n^2만 보고 0(N^2) 라고 표현

 

장점   

                 1. 알고리즘이 단순하다.

                 2. 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다.

                 3. 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다 => 제자리 정렬

 

단점   

                  1. 시간복잡도가 O(N^2)으로 , 비효율적이다.

                  2. 불안정 정렬(Unstable Sort)이다.