[자료구조] Select Sort (선택 정렬)

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

 

개념

리스트의 가장 작은 값을 선택하여 앞으로 하나씩 가져오는 방식 (오름차순)

1. 주어진 리스트 중에 최소값을 찾음
2. 그 값을 맨 앞에 위치한 값과 교체 (패스(pass))
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체

버블 정렬보다 성능이 좋음
작은 배열을 정렬할 때 삽입정렬이나 선택정렬이 더 빠름
제자리 정렬에 속함

 

시간복잡도

(Worst Case = Best Case = Average Case)

비교 - O(n^2)
교환 - O(n)

 

예제 코드

void selectSort(int array[], int n)
{
  int temp;

  for (int i = 0; i < n - 1; ++i)
  {
    int index = i;
    for (int j = i + 1; j < n; ++j)
    {
      if (array[j] < array[index])
        index = j;
    }
    temp = array[i];
    array[i] = array[index];
    array[index] = temp;
  }
}