[알고리즘 JS] 선택 정렬 알고리즘 : Selection Sort Algorithm

유데미 쉽게 배우는 JavaScript 알고리즘 입문 강의의 내용을 정리한 글입니다.

정렬 알고리즘이란?

일단 정렬 알고리즘이란, 말그대로 주어진 범위 내의 불규칙적으로 나열된 데이터들의 순서를 일정 기준으로 정렬해주는 알고리즘이다. 

정렬 알고리즘에는 여러 종류가 있는데, 크게 선택 정렬, 버블 정렬, 퀵 정렬, 삽입 정렬, 병합 정렬 등이 있다. 

그 중 가장 첫 번째로 다룰 선택 정렬 알고리즘은, 다른 정렬 알고리즘을 배우기 전에 간단하게 정렬 알고리즘을 경험해 볼 수 있는 알고리즘인 것 같다. (다른 정렬 알고리즘은 아직 몰라서...)

선택 정렬 알고리즘이란?

• 말 그대로 데이터 하나를 선택해서 해당 데이터를 기준으로 작거나(오름차순), 큰(내림차순) 데이터가 있는지 비교해 선택된 데이터와 계속해서 자리를 바꾸는 알고리즘이다.
• 모든 반복을 끝내면 오름차순 기준으로 배열의 오른쪽에 가장 작은 데이터가 오게 되는데, 이 때 반복은 데이터의 길이가 N일 때, N - 1만큼 반복한다.
• 반복 횟수가 N - 1인 이유는, 만약 5개의 데이터가 있다고 할 때, 1회전에 이미 가장 작은 데이터가 결정이 된다. 같은 방식으로 4번째 자리까지 정렬이 완료되었을 때, 남은 하나의 데이터(5번째 마지막 데이터)는 굳이 정렬을 하지 않아도 이미 자리가 바뀌어 정렬이 완료된 상태이기 때문이다! 

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

아래 코드를 보면서 더 자세하게 살펴보자!

• 3, 2, 1, 5, 4 라는 무작위 순서의 숫자가 존재하는 배열 data가 있다.
• 먼저 i번째 인덱스로 데이터를 "선택"하기 위해서, 바깥쪽 for문에서 N - 1회만큼 반복 조건을 설정한다.
• 안쪽 for문에서는, i와 나머지 데이터들을 비교해주기 위해서, i의 바로 다음 순번 데이터부터 마지막 N번째 데이터까지 돌 수 있도록 조건을 설정한다.
• 오름차순 정렬 기준으로 선택된 요소, data의 i번째 요소가 j번째 요소보다 크면, i번째 자리에 더 작은 요소인 j가 와야 하므로 swap을 시켜준다. 
• swap을 할 때, temp라는 임시 변수를 만들어 그 곳에 데이터를 잠시 저장한 뒤에 자리를 바꾸고 재할당한다. 

(() => {
  let data = [3, 2, 1, 5, 4];
  let N = data.length;

  for (let i = 0; i < N - 1; i++) {
    for (let j = i + 1; j < N; j++) {
      if (data[i] > data[j]) {
        let temp = data[i];
        data[i] = data[j];
        data[j] = temp;
      }
    }
    console.log(i + 1, '회전: ', data);
  }
})();

• 모든 반복문이 종료되었을 때 콘솔을 확인하면 아래와 같다.

/*
1 회전:  [ 1, 3, 2, 5, 4 ]
2 회전:  [ 1, 2, 3, 5, 4 ]
3 회전:  [ 1, 2, 3, 5, 4 ]
4 회전:  [ 1, 2, 3, 4, 5 ]
*/

+ 시간 복잡도 / 공간 복잡도

선택 정렬 알고리즘은 2중 반복을 도는 만큼 효율이 그렇게 좋은 정렬 알고리즘은 아니다.

시간 알고리즘을 빅 오 표기법으로 나타내면 O(n^2) 이고, 공간 복잡도는 O(n) 이다. 

다른 더 빠른 정렬 알고리즘들이 많이 있으니 빨리 공부하면 좋을 것 같다.(?)