TIL. 124 선택 정렬

선택 정렬 (Selection sort)

버블 정렬이 비교하고 바로 바꿔 넣는 걸 반복한다면 이 정렬은 1번째부터 끝까지 훑어서 가장 작은 게 1번째,
2번째부터 끝까지 훑어서 가장 작은 게 2번째……해서 (n-1)번 반복한다.
이 정렬은 인간이 흔히 사용하는 정렬 방식을 가장 많이 닮았다.
어떻게 정렬이 되어 있든 일관성 있게 에 비례하는 시간이 걸린다는 게 특징이다.

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

비슷한 것으로는 이중 선택 정렬(Double Selection Sort)도 있다.
이중 선택 정렬은 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 최솟값은 1번째와 바꾸고
최댓값은 끝과 바꾼 다음 훑는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 방식이다.
이 방법을 쓰면 반복 횟수가 반으로 줄어든다.

# 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://blog.tomclansys.com/53?category=1066976 [톰 클란시의 IT 블로그:티스토리]