Algorithm JS - 선택 정렬

jiny·2022년 9월 5일

JavaScript Algorithm

목록 보기

1/23

선택 정렬

가장 작은 값을 탐색한다음 Swap을 통해 앞부분에 배치시키는 정렬방식

과정
1. 주어진 리스트 중에 최소값을 찾기
2. 그 값을 맨 앞에 위치한 값과 교체(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체

Big O

최악

o(n2)

최상

o(n2)

평균

o(n2)

장점

코드 구현이 쉬운 편
정렬이 진행됨에 따라 속도는 빨라지는 속성을 가짐
버블 정렬보다 값의 복사와 이동이 적어 비교적 빠른 편

단점

데이터의 크기가 커질수록 효율이 떨어짐(a to z를 돌며 최솟값을 찾기 때문)
데이터의 정렬 속도가 o(n2)로 고정적으로 걸리기 때문에 퀵, 삽입 정렬에 비해 속도가 좋지 않음

소스 코드

/**
 * 선택 정렬
 * ▣ 문제
 * N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 버블정렬입니다.
 * ▣ 입력설명
 * 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
 * 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
 * ▣ 출력설명
 * 오름차순으로 정렬된 수열을 출력합니다.
 * ▣ 입력예제 1
 * 6
 * 13 5 11 7 23 15
 * ▣ 출력예제 1
 * 5 7 11 13 15 23
 */

function solution() {
     let answer = require('fs').readFileSync(__dirname+'/input.txt').toString().trim().split("\n").slice(1).join().split(' ').map(i=>Number(i));
     let temp = 0;
     for(let i = 0; i < answer.length - 1; i ++) {
          let idx = i;
          for(let j = i + 1; j < answer.length; j++) {
               if(answer[j] < answer[idx]) idx = j
          }
          temp = answer[idx];
          answer[idx] = answer[i];
          answer[i] = temp;
     }
     return answer;
}

console.log(solution())