목록기수정렬 (1)

홍카나의 공부방

[자료구조] 기수 정렬(Radix Sort)

기수 정렬이라고 번역되는 Radix Sort, 자릿수 정렬이라고 생각하면 이해가 더 쉬울 것이다. 기수 정렬은 말 그대로 자릿수와 정수를 이용해서 정렬을 하는데, 정수로 이루어진 배열을 정렬할 때 유독 사용하기 좋다. 한 번 살펴보자.  0부터 9를 담을 수 있는 큐 10개를 만든다. 여기서 큐를 만든 것은, 먼저 들어간 원소를 쉽게 제거할 수 있는 FIFO 자료구조를 사용한 것이다. 큐 대신에 리스트나 덱을 이용해도 구현은 할 수 있겠지만, 큐를 예시로 들어보겠다. 입력으로 예시 삼을 리스트가 [170, 45, 75, 90, 2, 802, 2, 66] 라고 가정하자. 여기서 각 정수들의 1의 자릿수만 살펴보면 다음과 같다. [0, 5, 5, 0, 2, 2, 2, 6] 1의 자릿수의 숫자에 맞게 해당 숫..
Data Structure + Algorithm 2024. 8. 5. 15:19
이전 Prev 1 Next 다음