HYUNGI'S TECH BLOG

기본 정렬 알고리즘 구현하기

이 기본 정렬 알고리즘은 직접 손 코딩 할 수 있을 정도로 코드를 익혀야 하기 때문에 반복 복습을 위해 블로그 포스팅을 해두기로 했다.
코딩 테스트 문제를 풀때 내장된 sort 함수를 사용해서 간편하게 정렬을 해서 문제 해결을 하지만, 기존에 있는 정렬 알고리즘의 구현을 이해하고 필요에 따라 기존 정렬 알고리즘을 응용해서 새로운 알고리즘을 만들어 낼 수 있는 능력도 필요하다.
그럼 자바스크립트 언어로 코딩테스트를 준비하고 있기 때문에 자바스크립트로 각 기본 정렬 알고리즘을 구현 및 정리를 해보겠다.

선택정렬(Selection sort) - O(N^2) 시간복잡도/정수 6만개 기준, 10.842(sec)

우선 선택 정렬에 대해서 코드 구현을 하기 전에 간단하게 선택정렬을 어떻게 구현해야 되는지 설명을 하겠다.
선택정렬은 버블정렬과 같이 1회 순회에 한 개 요소의 위치가 결정이 된다. (가장 작은 값(왼쪽부터 오른쪽으로) 결정)
이중 for-loop의 형태로 i: 0 ~ arr.length, j: i+1 ~ arr.length로 순회를 한다.
그리고 j의 범주로 순회를 하면서 가장 작은 값의 index를 찾는다. 가장 작은 값의 index를 찾았다면, 최소값의 index위치와 i번째 index위치를 바꿔준다. 이 과정을 i의 범주로 순회를 하면 정렬이 완료된다.
그럼 코드로 한 번 구현을 해보겠다.

for (let i = 0; i < arr.length; i++) {
  let index = i;
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[j] < arr[index]) index = j;
  }
  [arr[i], arr[index]] = [arr[index], arr[i]];
}