MSD 대 LSD 기수 정렬

LSD 기수 정렬을 사용하는 이유가 확실하지 않습니다. MSD의MSD 대 LSD 기수 정렬

장점 :

하나는 사용할 수

이

그것은 (이 빨리 순서에 대한 결정 CA) 그것은 항상 전체 문자열을 검색 할 필요가 없습니다
가변 길이의 문자열을 처리 할 수 있습니다 삽입 정렬 : 정렬 계산의 단점을 피할 수 있습니다.

출처

2014-01-12 user1377000

문자열을 사전 순으로 정렬하지 않고 숫자 순으로 정렬하는 것을 고려하십시오. 보다 자세한 답변을 원하시면 http://cstheory.stackexchange.com/ – beaker

@ beaker-cstheory.stackexchange.com을 연구 레벨 CS 문제로 사용해보십시오. 나는 이것이 이것이 거기에서 적절할 것이라고 생각하지 않는다. – templatetypedef

@templatetypedef 잘못된 잘라 내기 및 붙여 넣기 작업입니다. 죄송합니다. http://cs.stackexchange.com/에 가려고했는데 어떤 이유로 페이지 하단의 편리한 목록에 나타나지 않습니다. – beaker

MSD 기수 정렬을 통한 LSD 기수 정렬의 한 가지 장점은 LSD 기수 정렬이 안정된 정렬이라는 것입니다. 동일한 키로 정렬 할 요소가 여러 개인 경우에는 동일한 순서로 끝납니다. LSD 기수 정렬을 실행할 때 정렬 된 출력을 표시하지만 MSD 기수 정렬을 실행하지 않을 수도 있습니다. 키가 문자열 또는 정수인 키/값 쌍을 정렬하고 원래 상대 순서를 유지하려는 경우 LSD 기수 정렬이 MSD 기수 정렬보다 바람직합니다.

희망이 도움이됩니다.

출처

2014-01-12 17:29:06 templatetypedef

MSD 기수가 안정적인 정렬 알고리즘이 아닌 이유는 무엇입니까? 여기에서도 우리는 숫자를 정렬하기 위해 안정적으로 계산하는 정렬을 사용하지만 MSB에서 맞습니까? – Zephyr

@Zephyr MSD 기수 정렬 (특히 이진 MSD 기수 정렬)의 일부 구현은 quicksort와 같은 불안정한 분할 전략을 사용합니다. 안정적으로 할 수는 있지만 필수는 아닙니다. 이에 대한 자세한 내용은 "binary quicksort"를 참조하십시오. – templatetypedef

예 quicksort를 사용하면 불안정합니다. 그러나 왜 우리가 계산 분류를 사용하여 양동이 안의 MSB가 동일한 요소를 정렬 할 수 없다고 말할 수 있습니까? – Zephyr

@templatetypedef는 아름답게 요약했습니다.
MSD 기수 정렬은 lexicographic order의 키를 정렬하는 데 유용합니다.
작업 예제와 명확한 정보는 wikipedia을 살펴보십시오.

출처

2014-01-12 19:13:45

고맙습니다. 정수에 대한 사전 식 순서는 자연 순서입니다. 나는 두 기수 정렬 변형이 달성하려고하는 것에 차이가 있다고 생각하지 않는다. – user1377000

@ user1377000 예, 기본적으로 동일한 방향에서 시작하여 제공되는 정수와 문자열에서 비슷하게 수행합니다. 일반적으로 사전 식 순서는 왼쪽에서 오른쪽으로, 그리고 오른쪽에서 왼쪽 순으로 비대칭 순서로 정렬됩니다. –

나를위한 LSD 기수 정렬의 가장 큰 장점은 분기없는 알고리즘이기 때문에 속도입니다. 비교적 짧은 고정 길이 키에 대해 LSD 기수 정렬을 가능한 가장 빠른 정렬 알고리즘으로 만듭니다. LSD의 안정성 또한 좋은 점입니다.

출처

2014-01-12 20:49:10

MSD 대 LSD 기수 정렬

답변

관련 문제