[알고리즘] #3. 선택정렬

1. 선택정렬(Selection Sort) 알고리즘

• 제자리 정렬(in-place sorting) 알고리즘의 하나
  → merge sort나 quick sort처럼 요소분할시 추가적인 공간이 필요하지 않은 정렬. 버블, 삽입, 선택정렬 등
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떠한 원소를 넣을지 선택하는 알고리즘

• 주어진 배열 중 최소값을 찾는다.
• 그 값을 맨 앞에 위치한 값과 교체
• 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체
• 하나의 원소만 남을 때까지 위 방법을 반복

 

2. 선택정렬 알고리즘의 구현

# 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]);
  }
}

 

 

 

3. 선택정렬 알고리즘의 특징

3-1. 장점

• 구현이 쉽다.
• 자료 이동 횟수가 미리 결정됨.
• 비교하는 횟수에 비해 교환이 적게 일어남.

3-2. 단점

• 안정성을 만족하지 않는다.
  → 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있다.
• 시간이 오래 걸려 비효율
  → 버블정렬에 비해 조금 더 빠른 정렬방식

 

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

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

참고) https://cocoon1787.tistory.com/687

[Algorithm] 선택 정렬(Selection Sort) 이란?

참고) https://yabmoons.tistory.com/250

[ 정렬 ] 정렬별 장단점 및 시간복잡도