선택 정렬

선택 정렬의 기본 개념

선택정렬은 배열에서 가장 작은 원소를 선택해 앞으로 보내는 방식의 단순한 정렬 방식이다.

제자리 정렬

선택 정렬은 제자리 정렬인가?

선택 정렬은 제자리 정렬이다.
선택 정렬은 배열을 정렬할 때,
현재 인덱스의 값이 최소값보다 작다면 기존 배열 내에서 스와이프만 해주면 된다.
즉 추가 메모리가 필요하지 않으므로 제자리 정렬 방식 중 하나이다.

안정적 정렬

선택 정렬은 안정적 정렬인까?

안정적 정렬이 아니다.
안정적 정렬이란 같은 값을 가진 원소들의 상대적 순서가 유지되는 정렬이다.
최소값을 맨 앞 인덱스로 스와이프하는 과정에서 순서가 바뀔 수 있기 때문이다.

가령 (5,A), (3,A), (5,B), (3,B)가 있다면
-> (3,A), (5,A), (5,B), (3,B)
-> (3,A), (3,B), (5,B), (5, A)

(5,A)와 (3,B)가 스와이프하면서 (5, A)가 (5,B)보다 뒤에 위치할 수 있다.

구현 코드

void select_sort(int list[], int n) {
	int i, j, least, tmp;
    for (i = 0; i < n-1; i++) {
    	least = i;
      for (j = i+1; j < n; j++) {
      	if (list[least] > list[j]) least = j;
      }
      if (i != least) swap(list, i, least);
   }
}

void swap(int list[], int idx1, int idx2) {
  int temp = list[idx1];
  list[idx1] = list[idx2];
  list[idx2] = temp; 
}

시간복잡도

1. 평균 시간복잡도: O(n^2)
2. 최악 시작복잡도: O(n^2)