Radix Sort1 [JAVA] 기수정렬(Radix Sort) 개념과 코드 구현 기수(자릿수)별로 비교 없이 수행하는 정렬 알고리즘이다. 기수에 따라 원소를 버킷에 집어넣기때문에 비교 연산이 불필요하다. 해당 과정을 일의자리부터 가장 큰 자릿수까지 반복하면서 정렬한다. 각 자릿값에 대해 계수정렬을 수행한다. 데이터 크기에 비례하여 추가적인 메모리 공간이 많이 필요하다는 단점이 있다. 구 분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 기수정렬 O(d *(n+k)) O(d*(n+k)) O(d*(n+k)) O(n+k) Y * d: 가장 큰 자릿수의 수, n: 데이터의 개수, k: 버킷의 개수 알고리즘 1. 정렬할 데이터 중 가장 큰 자릿수를 구한다. 2. 데이터의 일의 자리부터 가장 큰 자릿수까지 자릿수 별로 정렬을 수행한다. 3. 각 자릿수 별로 정렬하기.. 2023. 4. 17. 이전 1 다음