자바스크립트의 선택정렬(Selection Sort)

Haizel·2023년 11월 16일

선택정렬 정렬

💡 알바알천 프로젝트

목록 보기

8/11

지난 버블정렬(Bubble Sort)에 이어 자바스크립트의 선택정렬(Selection Sort)에 대해 알아보자.

이 글은 JavaScript 알고리즘 & 자료구조 마스터클래스를 참고하여 작성되었습니다.

01. 선택정렬(Selection Sort)의 개념

큰 값을 배열 끝에 위치시키는 버블 정렬과 달리 선택 정렬은 원소 중 가장 작은 값을 선택해 맨 앞에 위치시키는 과정을 반복하여 정렬하는 알고리즘을 말한다.
즉 버블 정렬은 맨 뒤(오른쪽)부터 정렬 요소를 누적했다면, 선택 정렬은 맨 앞(왼쪽)부터 누적한다고 생각하면 된다.

02. 정렬 방법

루프를 돌 때마다 오른쪽 값과 비교하여 더 큰 값과 교환했던 버블 정렬과 달리 선택 정렬은 한 루프를 돌면서 최소 값을 찾아 갱신하고 해당 루프가 종료되면 맨 앞 요소와 자리를 바꾼다.

다음 루프부터는 정렬된 요소 다음 요소부터 확인하게 된다.

출처 : visualgo

선택 정렬의 작동 방식을 정리해보자면 다음과 같다.

최소값을 저장할 변수를 선언하고, 배열의 첫 번째 값을 할당한다.

루프를 돌며 가장 작은 변수 값을 찾아 갱신한다.
*이때 저장하는 것은 최소 값의 값(value)이 아닌 값의 위치(index)이다.

루프가 종료되면 최소 값과 맨 앞 요소의 자리를 바꾼다.

모든 정렬이 완료될 때까지 이 과정을 반복한다.

03. 선택 정렬 구현

const selectionSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j;
      }
    }
    if (i !== lowest) {
      [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
    }
  }
  return arr;
};

console.log(selectionSort([0, 2, 34, 22, 10, 19, 17])); // [ 0, 2, 10, 17, 19, 22, 34 ]

버블정렬과 마찬가지로 중첩된 반복문을 사용해 구현한다.

첫번째 반복문 상단에 최소값을 저장할 변수를 선언하고, 배열의 첫번째 요소의 index 값을 할당한다.

안쪽 반복문은 i+1부터 시작해 현재 요소와 최소값을 비교한다.

만약 현재값이 더 작다면 최소값을 갱신한다.

첫 번째 루프가 종료되고 최소값이 갱신되었을 경우 맨 앞 요소와 자리를 바꾼다.

다음 루프는 정렬된 요소 다음부터 확인하며 반복한다.