Selection Sort(선택정렬)

1. 선택정렬

• 제자리 정렬 알고리즘의 하나
• 다음과 같은 순서로 정렬함
  • 주어진 리스트 중에 최소값을 찾는다.
  • 그 값을 맨 앞에 위치한 값과 교체한다
  • 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체
• 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 O(n^2)만큼의 시간이 걸린다
• 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 성능상의 이점이 있음
• 복잡도:
  • 최악(시간): O(n^2) 비교, O(n) 교환
  • 최선(시간): O(n^2) 비교, O(n) 교환
  • 평균(시간): O(n^2) 비교, O(n) 교환
  • 공간복잡도: O(1) 예비

2. 수도코드

i를 0부터 n까지 반복:
	배열[i]부터 배열[n-1]까지 차례로 비교
    가장 작은 값이 배열[j]
    배열[i]와 배열[j]의 값을 서로 맞바꿈

3. 다른 정렬들과 비교

• 거품정렬: 시간복잡도 O(n^2)인 정렬 알고리즘에서 선택정렬은 버블 정렬보다 항상 우수
• 삽입정렬: 삽입정렬은 k번째 반복 이후, 첫번째 k번째 요소가 정렬된 순서로 온다는 점은 유사하지만, 선택정렬은 k+1번째 요소를 찾기위해 나머지 모든 요소들을 탐색. 삽입정려은 k+1번째 요소를 배치하는데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있음.
• 합병정렬: 선택정렬은 합병정렬과 같은 분할 정복 알고리즘을 사용하지만, 일반적으로 큰 배열보다 작은 배열(10~20개미만에서) 더 빠름 따라서 충분히 작은 하위 목록에만 삽입 혹은 선택정렬을 이용해서 최적화하는 게 좋음

4. 코드 구현

• java

void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
    return list;
}

• javascript

function selectionSor(list) {
  let indexMin, tmp;
    
  for(let i=0; i<list.length-1; i++) {
    indexMin = i;
  	for(let j=i+1; j<list.length; j++) {
      if(list[j] < list[indexMin]) {
        indexMin = j;
      }
      tmp = list[indexMin];
      list[indexMin] = list[i];
      list[i] = temp;
    }
  }
  return list;
}