Radix Sort (기수 정렬)

| O(n) 정렬 비교 정렬의 하한은 O(nlogn)이지만 입력된 자료의 원소가 제한적인 성질을 만족하는 경우 O(n) 정렬이 가능하다. 대표적인 O(n) 정렬의 알고리즘으로는 Counting Sort와 Radix Sort가 있다. | Radix Sort Radix Sort 또한 자료의 원소가 제한적인 성질을 만족하는 경우 사용 가능한 O(n) 정렬 방법이다. 원소의 자릿수가 d자리 이하인 N개의 수들로 이루어진 경우 O(d * N)의 시간 복잡도를 갖는 정렬방법이다. 소개할 Radix Sort 구현 방법은 Counting Sort를 활용하는 방법이다. 낮은 자리부터 정렬을 하고 정렬된 순서를 유지하면서 보다 높은 자리를 정렬하는 과정에서 Counting Sort가 활용된다. 따라서 개수를 셀(Count..
IT/자료구조, 알고리즘 2022. 9. 27. 21:35
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/11   »
일 월 화 수 목 금 토
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함