선택 정렬

HYl·2022년 5월 2일

알고리즘 코딩테스트

Algorithm

목록 보기

2/3

선택 정렬

Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

Selection Sort와 Insertion Sort를 헷갈려하시는 분들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하시면 편합니다.

문제 설명

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

입력 설명

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

13 5 11 7 23 15

출력 설명

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

5 7 11 13 15 23

풀이 과정

이중 for문을 돌아야 한다.
- j는 i 뒤부터 시작한다.
i는 0부터 끝까지 돌면서 제일 작은 숫자를 제일 앞에 가져온다.
idx라는 변수에, 제일 작은 숫자의 index 값을 저장한다
- 처음에는 idx를 i로 초기화 한다.
두 번째 for문을 다 돌고 나면, arr[j]와 arr[idx]의 값을 서로 교환한다.

풀이 코드

function solution(arr) {

  for(let i = 0; i < arr.length; i++) {
    let idx = i; // i로 초기화

    // j는 i 뒤편
    for(let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[idx]) idx = j; // 작은 값의 위치를 idx에 저장
    }

    [arr[i], arr[idx]] = [arr[idx], arr[i]]; // arr[j]와 arr[idx]의 값을 서로 교환
  }

  return arr;
}

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

시간복잡도

데이터의 개수가 n개라고 했을 때,

첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1

두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2

...

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸립니다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일합니다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.

장점

Bubble sort와 마찬가지로 알고리즘이 단순합니다.
정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적입니다.
Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)