[알고리즘] 선택 정렬 with JS

선택정렬(Selection sort)

배열에서 가장 작은 값을 찾아서 배열의 맨 앞에 위치시키고, 그 다음 작은 값을 찾아서 두 번째 위치에 위치시키는 방식으로 정렬하는 알고리즘 입니다.

---

선택정렬 실행 과정

1. 배열의 첫 번째 원소를 제외한 나머지 원소들 중 가장 작은 값을 찾습니다.
2. 가장 작은 값과 배열의 첫 번째 원소를 교환합니다.
3. 배열의 두 번째 원소를 제외한 나머지 원소들 중 가장 작은 값을 찾습니다.
4. 가장 작은 값과 배열의 두 번째 원소를 교환합니다.
5. 위의 과정을 반복해서 전체 배열이 정렬될 때까지 반복합니다.

---

선택정렬 코드

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

 

위 코드를 각각 해석해서 정리해보았습니다.

/** for 루프를 사용해 배열 arr을 탐색합니다. i는 현재 탐색 중인 위치를 나타냅니다.
배열의 마지막 요소는 비교할 필요가 없으므로, arr.length - 1까지만 탐색합니다.*/
for (let i = 0; i < arr.length - 1; i++) {

 

** 왜 arr.length - 1 이 되나요?

선택 정렬은 각 반복마다 최소값을 찾아 맨 앞으로 보내기 때문에, 매 반복마다 정렬된 요소들은 배열의 맨 앞에 위치하게 됩니다. 이 말은 즉, i번째 요소를 정렬할 때, 0부터 i-1번째 요소들은 이미 정렬이 완료되었다는 것을 의미합니다.

 

그렇기 때문에 마지막 요소는 이미 정렬된 상태이므로 비교할 필요가 없게 됩니다. 따라서 마지막 요소를 비교하는 것은 불필요한 연산이므로, i < arr.length - 1 조건을 사용하여 마지막 요소를 제외하고 정렬하도록 구현 합니다.

---

// minIndex 변수를 초기화합니다. 이 변수는 현재까지 발견된 가장 작은 요소의 인덱스를 저장합니다.
let minIndex = i;

// 내부 for 루프를 사용해 i 위치 이후의 모든 요소를 탐색합니다. j는 현재 탐색 중인 위치를 나타냅니다.
for (let j = i + 1; j < arr.length; j++) {

 

/** 현재 요소가 현재까지 발견된 가장 작은 요소보다 작으면, minIndex 에 인덱스 j 를 할당합니다.
minIndex는 배열 arr에서 가장 작은 요소의 인덱스를 가리킵니다. */
if (arr[j] < arr[minIndex]) { minIndex = j; }

/** i 위치에는 현재까지 발견된 가장 작은 요소를 놓습니다. 만약 minIndex와 i가 같지 않다면, 
즉, i 위치에 있는 요소가 현재까지 발견된 가장 작은 요소가 아니라면,
i 위치와 minIndex 위치의 요소를 교환합니다. */

if (i !== minIndex) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; }

 

// 반복문이 끝나면, 배열 arr은 선택 정렬 알고리즘을 사용해 정렬된 상태가 됩니다. 이 배열을 반환합니다.

} return arr; }

 

---

시간복잡도

• 최악의 경우 (Worst Case) : 입력 배열이 역순으로 정렬되어 있는 경우로, n-1번의 비교를 수행하고, 2번의 자리 교환을 수행해야 합니다. 따라서 연산 횟수는 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 로 O(n^2) 입니다.
• 보통의 경우 (Average Case) : 입력 배열이 랜덤하게 주어졌을 때, 비교 횟수는 최악의 경우와 동일하지만 자리 교환 횟수는 더 적을 수 있습니다. 따라서 연산 횟수는 최악의 경우와 동일하게 O(n^2) 입니다.
• 최적의 경우 (Best Case) : 입력 배열이 이미 정렬되어 있는 경우로, 비교는 n(n-1)/2 번 수행하지만 자리 교환 횟수는 0번입니다. 따라서 연산 횟수는 O(n^2) 이지만 최악의 경우보다는 빠릅니다.

 

참고로, (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 는 1부터 n-1까지의 모든 자연수의 합을 나타내는 수학적 공식 입니다. 

---

공간복잡도

주어진 배열 안에서 정렬을 수행하므로, 추가적인 메모리 공간을 필요로 하지 않습니다. 따라서 공간복잡도는 O(1) 입니다