반응형 기수정렬1 [자료구조] 기수정렬(Radix Sort) 기수정렬이란 - 데이터들의 값을 비교연산을 하지 않는 알고리즘이다. - 데이터를 구성하는 기본요소, 즉 기수를 이용하여 정렬을 진행하는 방식이다. - 낮은 자리부터 정렬하는 LSD, 높은자리부터 정렬하는 MSD가 있다. - MSD는 추가적인 연산을 필요로 하기때문에 LSD를 선호한다. 단점 - 자릿수가 없는 것은 정렬할 수 없다.(부동 소숫점) - 중간 결과를 저장할 bucket 공간이 필요하다. - 시간복잡도 : O(n) void countSort(int arr[], int n, int exp) { int buffer[n]; int i, count[10] = {0}; // exp의 자릿수에 해당하는 count 증가 for (i = 0; i < n; i++){ count[(arr[i] / exp) % 1.. 2024. 1. 15. 이전 1 다음 반응형