Radix Sort
-
알고리즘, Sort, Radix SortData Structure & Algorithm 2024. 6. 18. 17:54
Radix Sort(기수 정렬)은 정수나 문자열의 자릿수를 기준으로 정렬하는 효율적인 정수 정렬 알고리즘입니다. 이 알고리즘은 주로 양의 정수나 고정 길이의 문자열을 정렬하는 데 사용되며, 시간 복잡도가 O(d * (n + k))로, 비교 기반 정렬 알고리즘보다 더 효율적일 수 있습니다. 여기서 d는 데이터의 최대 자릿수, n은 요소의 수, k는 기수(예: 10진법에서는 10)입니다.기본 개념기수 정렬은 LSD(Least Significant Digit)와 MSD(Most Significant Digit) 두 가지 방법으로 나뉩니다:LSD 방식: 가장 작은 자릿수부터 시작하여 큰 자릿수 방향으로 정렬합니다.MSD 방식: 가장 큰 자릿수부터 시작하여 작은 자릿수 방향으로 정렬합니다.LSD 방식은 일반적으로..