[JavaScript/section 7] 01 - 선택 정렬

📌 문제

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 문제이다. 정렬하는 방법은 선택 정렬이다.

 

🧐 선택 정렬이란 무엇일까?

• 제자리 정렬(in-place sorting) 알고리즘의 하나
  • 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
  • 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
  • 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.
  • ... 이하 생략
• 과정 설명
  1. 주어진 배열 중에서 최솟값을 찾는다.
  2. 해당 값을 맨 처음에 위치한 값과 교체한다.
  3. 맨 처음 위치를 제외한 나머지 요소들을 같은 방법으로 교체한다.
  4. (배열의 길이 - 1) 만큼 위의 1 ~ 3 과정을 반복한다.

 

📝 풀이

🧑🏻‍💻 나의 풀이 방법

function solution(arr) {
  let answer = arr;

  for (let i = 0; i < arr.length - 1; i++) {
    // i는 현재 정렬을 확정하고자 하는 위치(인덱스)
    let min = arr[i];
    let index = i;

    // 확정된 정렬을 제외한 나머지 요소들 중에서 최솟값을 찾는 과정
    for (let j = i + 1; j < arr.length; j++) {
      if (min > arr[j]) {
        min = arr[j];
        index = j;
      }
    }

    // 최솟값을 찾은 후 해당 값을 temp 변수를 사용해 교체하고 정렬을 확정한다.
    let temp = arr[i];
    arr[i] = arr[index];
    arr[index] = temp;
  }

  return answer;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

👨🏼‍🏫 강사님 풀이 방법

나의 풀이 방법과 유사하지만, 배열의 요소를 교체하는 방법으로 구조 분해 할당 구문을 사용한다.

구조 분해 할당 구문은 배열이나 객체의 속성을 해체하여 그 값을 개별 변수에 담을 수 있게 하는 JavaScript의 표현식이다.

[arr[i], arr[idx]] = [arr[idx], arr[i]];

 

// 강사님 풀이 방법
function solution(arr) {
  let answer = arr;

  for (let i = 0; i < arr.length - 1; 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;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

🙇🏻 참고한 사이트

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog