Selection Sort(선택 정렬)

출처) https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다.

키값과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.

<시간 복잡도>

출처) https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

<전체 코드>

# include <stdio.h>
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
# define MAX_SIZE 5

void selection_sort(int list[], int n){ // 선택 정렬
  int i, j, least, temp;

  for(i=0; i<n-1; i++){ // 마지막 키값은 자동 정렬 되므로 (숫자 개수-1)만큼 반복
    least = i;

    for(j=i+1; j<n; j++){ // 최솟값 탐색
      if(list[j]<list[least])
        least = j;
    }

    if(i != least){ // 최솟값이 자기 자신인 경우 값을 swap하지 않는다.
        SWAP(list[i], list[least], temp);
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {9, 6, 7, 3, 5};

  selection_sort(list, n); // 선택 정렬 수행

  for(i=0; i<n; i++){ // 정렬 결과 출력
    printf("%d\n", list[i]);
  }
}