6. 선택 정렬

출처: https://gmlwjd9405.github.io/images/algorithm-selection-sort/selection-sort.png

선택 정렬 (Selection sort)

선택  정렬을 실행했을 때 나오는 그림.

버블 정렬이 비교하고 바로 바꿔 넣는 걸 반복한다면 이 정렬은 1번째부터 끝까지 훑어서 가장 작은 게 1번째,

2번째부터 끝까지 훑어서 가장 작은 게 2번째……해서 (n-1)번 반복한다.

이 정렬은 인간이 흔히 사용하는 정렬 방식을 가장 많이 닮았다.

어떻게 정렬이 되어 있든 일관성 있게 에 비례하는 시간이 걸린다는 게 특징이다.

또한, 버블 정렬보다 두 배 정도 빠르다.

정렬 알고리즘 시간 복잡도 비교

• 단순(구현이 간단)하지만 비효율적인 방법
  
  삽입 정렬, 선택 정렬, 버블 정렬
  
  
• 복잡하지만 효율적인 방법
  
  퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

비슷한 것으로는 이중 선택 정렬(Double Selection Sort)도 있다.

이중 선택 정렬은 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 최솟값은 1번째와 바꾸고

최댓값은 끝과 바꾼 다음 훑는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 방식이다.

이 방법을 쓰면 반복 횟수가 반으로 줄어든다.

https://youtu.be/Ns4TPTC8whw

이해를 돕기위해. 배속을 하고 봐라!

---

예제 C코드

# 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;

  // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
  for(i=0; i<n-1; i++){
    least = i;

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

    // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
    if(i != least){
        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]);
  }
}

1싸이클
첫 번째 원소 9를 두 번째 원소부터 마지막 원소까지 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다.

이 과정에서 원소를 4번 비교한다.

2싸이클
두 번째 원소 6을 세 번째 원소로부터 마지막 원소까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 

이 과정에서 원소를 3번 비교한다.

3싸이클
세 번째 원소 7을 네 번째 원소로부터 마지막 원소까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다.

이 과정에서 원소를 2번 비교한다.

4싸이클
네 번째 원소 9와 마지막에 있는 원소 7을 비교하여 서로 교환한다.

---

참조 사이트

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

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#fn-13

정렬 알고리즘 - 나무위키

https://www.codecogs.com/latex/eqneditor.php

Online LaTeX Equation Editor - create, integrate and download