[자료구조 복습12] Radix Sort 기수정렬
해당 글은 geeks for geeks와 위키피디아 를 참고하여 쓰여졌습니다. 먼저 Radix sort가 어떻게 동작하는지 알아보자. Radix Sort는 요소 간의 비교 없이 동작하는 소팅 알고리즘 이다. 단순하게 생각하면 최댓값 n개의 배열을 만들고, 해당하는 수를 인덱스로 하는 배열 요소의 빈도수를 증가시킨 후 , 다시 배열을 돌면서 빈도수만큼 해당 인덱스를 출력해도 된다. 하지만 배열이 [1,2,10000,999,80] 이렇게 생긴 경우는 효율성이 매우 떨어진다. 이를 위해서 각 자리수를 비교해 나가며 정렬하는 Radix Sort를 학습해보자. 배열 [170, 45, 75 , 90 , 802 , 24 , 2 , 66 ] 을 예시로 들어보자. 1의자리수부터 최댓값 n의 최대 자리수까지 본다. 해당 ..
algorithm/자료구조 복습
2020. 4. 4. 15:44