TIL. 선택정렬 알고리즘 문제풀이

선택 정렬

선택 정렬(Selection Sort)은 배열이나 리스트를 정렬하는 간단한 비교 기반 알고리즘이다.

• 기본 원리는 전체 목록을 순회하면서 각 위치에 들어갈 가장 작은(또는 가장 큰) 요소를 선택하고, 그 요소를 해당 위치에 배치하는 것이다.
• 이 과정을 배열의 모든 위치에 대해 반복함으로써 전체 배열을 정렬한다.
  - 주어진 배열에서 최소값을 찾는다.
  - 이 최소값을 배열의 첫 번째 위치와 교환한다.
  - 배열의 첫 번째 위치를 제외한 나머지 배열에 대해 이 과정을 반복한다.

선택 정렬의 특징

• 비효율적인 시간 복잡도
  : 선택 정렬의 시간 복잡도는 평균적으로 O(n^2)이다. 배열의 크기가 n일 때, 이 알고리즘은 대략 n^2/2번의 비교와 n번의 교환을 수행한다. 😓

• 안정성
  : 선택 정렬은 안정적인 정렬 알고리즘이 아니다. 즉, 동일한 값의 원소가 입력에서의 순서를 유지하지 않을 수 있다.

• 제자리 정렬(in-place sorting): 선택 정렬은 추가적인 메모리를 거의 사용하지 않고 배열 내에서 정렬을 수행한다. 따라서, 제자리 정렬 알고리즘으로 분류된다.

+) 안정적인 정렬 알고리즘이란 동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에도 변경되지 않는 성질을 의미한다. 예를들어 [3a, 3b, 2] 에서 2가 가장앞으로 올 경우 선택 정렬 과정에서 [2, 3a, 3b,] 가 아니라 [2, 3b, 3a] 로 3의 상대적 위치가 바뀔 수 있다.

선택 정렬이 사용되는 경우

• 작은 데이터 세트
  : 데이터의 양이 많지 않을 때(예: 수십 개 정도의 요소), 선택 정렬은 간단하고 직관적인 방법으로 충분히 빠른 성능을 낼 수 있다.

• 메모리 사용 제약이 있는 경우: 추가적인 메모리 할당이 제한적인 환경에서는 제자리 정렬 알고리즘인 선택 정렬이 유리할 수 있다.

• 단순성과 가독성을 중시하는 경우: 선택 정렬은 구현이 매우 간단하므로, 알고리즘을 처음 배우는 학습자에게 정렬 알고리즘의 기본 개념을 이해시키기에 좋다.

✍️ 하지만! 대부분의 실용적인 응용 프로그램에서는 더 효율적인 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)이 선택 정렬보다 선호되는데, 이는 더 큰 데이터 세트에 대해 더 나은 성능을 제공하기 때문이라고 한다. 🧐

문제 설명

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 선택정렬입니다.

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

▣ 출력설명
오름차순으로 정렬된 수열을 출력합니다.

▣ 입출력 예

input	output
6 13 5 11 7 23 15	5 7 11 13 15 23

풀이

👉 1차

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let cur = arr[i];
    let min = arr[i]; // ⭐️
    let minIndex = 0;

    for (let j = i + 1; j < arr.length; j++) {
      if (min > arr[j]) {
        min = arr[j]; // ⭐️
        minIndex = j;
      }
    }

    if (cur === min) continue;

    arr[i] = min;
    arr[minIndex] = cur;
  }

  return arr;
}

let arr = [6, 13, 5, 11, 7, 23, 15];
console.log('answer :', selectionSort(arr));

1. for문을 돌려서 배열방의 첫번째 요소와 비교할 2중 포문을 만든다.

2. 처음부터 끝까지 배열을 돌면서 가장 작은 숫자를 저장할 min을 정의한다.

• 가장 처음 순서에는 가장 작은 숫자를 모르니 그 숫자로 초기화한다. ⭐️
• min보다 작은숫자를 만날 때마다 업데이트한다. ⭐️

3. 해당숫자를 for문의 배열방의 첫번째 요소와 바꾼다.

4. 이어서 배열방의 두번째 요소를 기준으로 비교한다.

👉 2차

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let cur = arr[i];
    let minIndex = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }

    if (cur === arr[minIndex]) continue;

    arr[i] = arr[minIndex];
    arr[minIndex] = cur;
  }

  return arr;
}

console.log('answer :', selectionSort(arr));

• 최소값 인덱스 초기화 반식 변경
  : 1차 구현에서는 최소값을 찾기 위한 min 변수를 사용하고, 그 값을 각 반복마다 업데이트하면서 진행한다. 2차 구현에서는 최소값을 직접 저장하는 대신 최소값의 인덱스(minIndex)만을 저장하고 업데이트한다.

👉 3차

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[minIndex] > arr[j]) {
        minIndex = j;
      }
    }

    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // ⭐️
  }

  return arr;
}

console.log('answer :', selectionSort(arr));

• 구조 분해 할당을 통한 교환
  : 3차 구현에서는 배열의 원소를 교환할 때, 전통적인 방식(temp 변수를 사용하는 등) 대신 JavaScript의 구조 분해 할당 문법을 사용했다.😃 [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  이 방식은 기존방식보다 코드를 더욱 직관적이고 간결하게 만들며, 임시 변수 없이 두 변수의 값을 교환할 수 있는 효과적인 방법!
  👉 cur 변수가 필요없게 되었다.
  👉 if (cur === arr[minIndex]) continue 을 제거할 수 있게 되었다. 이는 배열의 특정 원소가 이미 최소값일 경우에도 구조 분해 할당을 사용하면 간단하게 처리할 수 있기 때문이다. 🧐

✍️ solution

function solution(arr) {
  let answer = arr;
  for (let i = 0; i < arr.length; i++) {
    let idx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[idx]) idx = j;
    }
    [arr[i], arr[idx]] = [arr[idx], arr[i]];
  }
  return answer;
}

console.log(solution(arr));

• 3차와 같은 방식이다.