기수 정렬에 안정된 정렬 알고리즘 만 사용해야하는 이유는 무엇입니까?

Question

기수 정렬에서 불안정한 정렬 알고리즘 (예 : 빠른 정렬)을 사용할 때의 위험을 이해하려고합니다. 또한 안정적인 알고리즘이 두 경우 모두 (즉, MSD 기수 정렬 및 LSD 기수 정렬)에 있어야합니까?

미리 감사드립니다.

Answer 1

MSD 기수 정렬은 일반적으로 실용적이지 않습니다. 각 통과 후에 가상 저장소를 연결할 수 없기 때문입니다. 8 비트 바이트 단위로 정렬하는 경우 첫 번째 패스 후에 256 개의 별도의 저장소가 있고 두 번 통과 한 후 65536 개의 저장소가 세 번 통과 한 후 16777216 저장소가됩니다.

LSD 기수 정렬은 가상 구획이 순서대로 연결되고 이후의 더 중요한 "자릿수"가 이전 통과에 의해 설정된 순서를 유지해야하기 때문에 안정되어야합니다. LSD 기수 정렬은 1900 년대 초로 거슬러 올라가는 오래된 카드 분류기가 어떻게 작동했는지를 참고하십시오.

http://en.wikipedia.org/wiki/IBM_card_sorter#Earlier_sorters