정수에 대한 기수 정렬을 수행하는 C++ 코드를 작성하려고합니다. 튜토리얼 온라인을 살펴본 결과, 각 정수를 오른쪽 버켓에 넣어야한다는 것을 알았습니다. 가장 중요한 숫자부터 시작합니다. 내 질문은, 기수 정렬에 대한 일반적인 알고리즘에서 0에서 9까지 10 개의 버킷이 필요합니까? 해당 버킷을 연결된 목록 (예 : * list1 ~~~ * list9)으로 할당하면 약간 이상하게 보일까요?기수 정렬 C++
감사합니다. 이것은 숙제가 아니라 호기심에서 나온 것입니다.
나는 이것이 C++ 질문이라고 생각하지 않는다. (Radix Sort는 C++에서 명확하게 구현 될 수 있지만) 적어도 링크 된 목록과는 아무 상관이 없다. 정렬은 각 자릿수에 대한 버킷에 효율적으로 액세스 할 수있는 자리별로 발생합니다. 이를 위해 목록은 너무 잘 작동하지 않지만 벡터는 그렇게됩니다. 각 버킷 안에는 목록을 사용할 수 있습니다.
필요한 버킷 수와 관련하여 답은 다음과 같습니다. 1보다 큰 모든 기초를 사용할 수 있으며 해당하는 버킷 수를 필요로합니다. 컴퓨터는 2의 거듭 제곱을 사용하는 컴퓨팅 능력이 특히 우수하기 때문에 10과 같은 다른 기반을 사용하는 것보다 훨씬 효율적입니다. 이상하게도, Wikipedia's article on Radix Sort은 10 진법을 사용합니다. 아마도 자유로운 선택의 기초에 대해 너무 많은 혼란을 피하기 위해서입니다.
'List0' ~'List9'에 있어야한다고 생각합니다. 또한, 그렇게 할 수 있습니다. 당신의 질문은 정확히 무엇입니까? – noMAD
내 질문에, 10 버킷을 정의하는 것이 필요합니까? –
목록 배열을 정의 할 수 있습니다. – qdot