자바스크립트 정렬 알고리즘 8 : Radix Sort, Counting Sort

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

여태껏 배운 Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort는 모두 comparison, 즉 element들 간의 비교를 통해 정렬을 하는 알고리즘이었다. 이들 정렬 알고리즘의 경우, 시간복잡도에서 최선은 O(n log n)이었는데, 이를 더 개선시킬 수는 없을까?

 

이를 개선시키는 것은 수학적으로 불가능하다고 한다. 그러나 element 간의 비교를 하지 않고 정렬을 할 경우, O(n log n)보다 더 나은 시간복잡도를 보여주는데, Radix Sort와 Counting Sort가 그러하다.

 

이 두개의 정렬 알고리즘은 데이터가 메모리 공간에 0과 1 두개의 숫자로 저장되어 있다는 점에 기반한 정렬 알고리즘이다. 이들의 적용 범위는 1) data가 반드시 숫자(특히 정수)여야만 하며, 2) 그 data들 또한 숫자의 범위가 정해져 있어야(ex. -300부터 10만까지) 사용이 가능하다. 숫자를 제외하면 어떤 데이터 타입에서도 Radix Sort와 Counting Sort를 사용하는 것은 불가능하다.

 

이들 알고리즘은 무척이나 복잡하므로, 궁금하면 아래 자료들을 참고해볼 수 있다.

☞ Radix Sort 자료

☞ Radix Sort Animation

☞ Counting Sort 자료

☞ Counting Sort Animation