선택 정렬

July 28, 2023

선택 정렬이란

선택 정렬은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다. 간단하게 말하면 해당 자리를 선택하고 그 자리에 오는 값을 찾는것이라고 생가하면 될 것 같습니다.

선택 정렬하는 과정을 간단히 정리하면 다음과 같습니다.

첫 번쨰 자료를 두 번째 자료 부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 둡니다.
두 번쨰 자료를 세번째 자료 부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째에 둡니다.
배열의 마지막 요소까지 위 과정을 반복합니다.

1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전부터는 두 번째 자료를 가지고 비교합니다.

선택 정렬 동작 과정

배열 [64, 25, 12, 22, 11]을 예를 들어 살펴 보겠습니다.

첫 번째 자리에 들어갈 가장 작은 값을 찾습니다, 가장 작은 값은 11 이므로 64와 11 자료의 위치를 바꿉니다.
```
[11, 25, 12, 22, 64]
```
두 번째 자리에 들어갈 가장 작은 값을 찾습니다, 두 번째 자료부터 가장 작은 값은 12 이므로 25와 12 자료의 위치를 바꿉니다.
```
[11, 12, 25, 22, 64]
```
세 번째 자리에 들어갈 가장 작은 값을 찾습니다, 세 번째 자료부터 가장 작은 값은 22 이므로 25와 22 자료의 위치를 바꿉니다.
```
[11, 12, 22, 25, 64]
```
네 번째 자리에 들어갈 가장 작은 값을 찾습니다, 네 번째 자료부터 가장 작은 값은 25 이므로 자료의 위치를 바꾸지 않습니다.
```
[11, 12, 22, 25, 64]
```

선택 정렬 구현 코드

function selectionSort(arr) {
  let temp;
  let minIndex;
  
  for (let i = 0; i < arr.length - 1; i++) {    
    minIndex = i;
    
    for (let j = i + 1; j < arr.length; j++) {
      if(arr[j] < arr[minIndex]) {
      	minIndex = j;
      }
    }
    
    if (minIndex !== i) {
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

시간 복잡도 & 공간 복잡도

시간 복잡도

선택 정렬의 최악의 경우 시간 복잡도는 O(N^2)입니다.
선텍 정렬의 평균적인 경우의 시간 복잡도는 O(N^2)입니다.
최선의 경우의 시간 복잡도는 O(N^2)입니다.

공간 복잡도

선택 정렬의 공간 복잡도는 O(1)입니다.

선택 정렬의 특징

안정적인 배열이 아닙니다.
제자리 정렬 알고리즘입니다.
이해하고 구현하기 쉽습니다.

참조

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

https://www.geeksforgeeks.org/selection-sort/

https://gyoogle.dev/blog/algorithm/Selection%20Sort.html