카운팅정렬1

• 

  210629 기수 정렬(Radix Sort) & 카운팅 정렬(Counting Sort) 비교 기반 정렬 알고리즘의 최대 효율 결국엔 숫자열의 모든 가능한 수열 중 하나를 찾아 내는 문제 모든 가능한 순열의 수 : n! 이를 Decistion Tree 를 통해 나타내면 이러한 과정을 통해 비교 기반 정렬 알고리즘의 최대 효율이 O(nlog n) 임을 알 수 있다 그렇다면 비료를 사용하지 않는 정렬 알고리즘은 어떤가? 제한적이지만 O(n)으로 수행가능한 방법들이 존재한다 카운팅 정렬(Counting Sort) 가장 큰 데이터에 따라 효율이 좌우됨 특정 데이터의 개수들을 저장해두고 순서대로 저장된 횟수대로 뱉어내어 정렬하는 방법 위와 같은 방법인데 파란색으로 표시한 1000 이 들어온 경우를 보면 왜 가장 큰 데이터에 효율이 좌우되는지 알 것이다. 가장 큰 데이터가 1000이기에 n이 8 밖에 .. 미가공 필기(알고리즘) 2021. 6. 30.