빠른 정렬 VS Radix Sort.

Question

코딩 시험에서, 나는 한때이 질문을했습니다.

오름차순으로 정수를 정렬하는 정렬 정렬이 있다고 가정하면, 속도를 가장 우선 순위를 지정하려는 알고리즘을 사용하지만 공간을 저장하고 싶습니다.

옵션은 다음과 같습니다.

• LSD RADIX 정렬
• 병합 정렬
• 빠른 정렬

LSD RADIX SORT 및 QuickSort 사이에 인수를 만들 수 있다고 생각합니다.

radix sort 은 $ o (kn) $ 및 quicksort 이 $ o (n \ log n) $ 및 최악의 경우 $ o (n ^ 2) $

radix sort 을 답변으로 선택했으나 다른 사람들이 말하고 싶은 것과는 궁금합니다.

Answer 1

입력 번호 수가 $ n $ 인 경우 $ \ theta (\ log n) $ 비트 및 최악의 경우 :

• radix sort는 $ o (n \ log n) $ $ o (n) $ 보조 공간.

• 고정 또는 무작위 피벗 선택이있는 QuickSort는 $ o (n ^ 2) $ 최악의 경우 시간과 $ o (\ log n) $ 보조 공간.

• 메르 토트는 $ o (n \ log n) $ 시간 및 $ o (n) $ < / span> 보조 공간.

Radix 정렬 및 병합 정렬은이 설정과 동일합니다.

QuickSort를 사용하여 무작위로 피벗 클래스 선택은 $ o (n \ log n) $ 의 시간 복잡성을 높게 사용할 수 있습니다. 결정자를 결정적으로 선택하여 요소를 가장 일정한 요소로 인한 두 세트의 두 세트로 분할하는 방식으로 $ o (n \ log)의 최악의 시간 복잡성으로 알고리즘을 제공합니다. n) $ 및 $ o (\ log n) $ 보조 공간.