제자리 정렬(in-place sorting) 알고리즘의 하나

Goal

  • 선택 정렬(selection sort) 알고리즘을 이해한다.
  • 선택 정렬(selection sort) 알고리즘을 c언어로 구현한다.
  • 선택 정렬(selection sort) 알고리즘의 특징
  • 선택 정렬(selection sort) 알고리즘의 시간복잡도를 이해한다.

들어가기 전

선택 정렬(selection sort) 알고리즘 개념 요약

선택 정렬(selection sort) 알고리즘의 구체적인 개념

선택 정렬(selection sort) 알고리즘의 예제

선택 정렬(selection sort) 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]);
  }
}

선택 정렬(selection sort) 알고리즘의 특징

선택 정렬(selection sort)의 시간복잡도

시간복잡도를 계산한다면

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

관련된 Post

References