[알고리즘] 기수정렬 (자바스크립트)

앞서 학습한 버블정렬, 선택정렬, 삽입정렬, 합병정렬, 퀵정렬은 '비교 정렬' 그룹에 속함. 주어진 시간에 두 가지 요소를 비교하는 방식. 이러한 비교 정렬은 한계점이 존재하며, 최선의 경우 O(n log n)의 복잡도를 갖는다 (합병정렬, 퀵정렬) 기수정렬 (Radix Sort) 비교를 수행하지 않는 특별한 정렬 알고리즘으로, 숫자 크기에 대한 정보를 이진수로 인코딩하여 정렬한다. 작동방식 배열 요소의 0의 자리 수부터 분리한다. 모든 값들은 (0-9) 사이로 레이블링되고, 이를 0 레이블의 먼저 들어온 값부터 꺼내 배열한다. 자릿수를 좌측으로 옮겨가며 레이블링을 반복하면, 정렬이 완료된다. 헬퍼함수 1. getDigit(원하는 숫자 인덱스 찾기) : 원하는 숫자가 어느 자릿수 인덱스에 위치하는지 반환..

원문링크 : [알고리즘] 기수정렬 (자바스크립트)