버켓 정렬 대 빠른 정렬

Question

일반 질문 : 버킷 정렬이 빠른 정렬보다 유리한 이유는 무엇입니까?

숫자가 스트림에서 수신되며 내 버킷은 (1,10) (11,20)과 같습니다.

그런 다음 버킷을 정렬 한 다음 함께 정렬합니다. 정렬 된 숫자가 있습니다.

OR

I 배열에 넣어 다음과 퀵

버킷 정렬들을 정렬 할 수 Bestcase O (N + K) worstcase (N^2); Quicksort : Bestcase O (1) Averagecase O (nlogn) worstcase (N^2);

그래서 우리는 정렬하고자하는 들어오는 정수 스트림과 같은 것들에 대해 버킷 정렬을 사용합니까? 각 버킷에있는 정수의 수를 기반으로 의사 결정을 할 수 있기 때문입니까?

감사

Answer 1

우리가 앞을 케이 알고,이 작은 경우 효율적으로 n 개의 * 로그 (N), 퀵의 평균이 때문에, 빠르게 퀵 이상 실행할 수 있습니다 종류의 다음 버킷 (< < N을 K) 버킷 정렬의 평균 인 (n + k) 이상이어야합니다.

즉,

sortedList = (n*log(n) > n + k) ? bucketSort(list) : quicksort(list); 

이 스트림을 위해 사용될 수있는 이유는, 현재 위치에서 일종의 그 버킷입니다. 매번 다시 정렬 할 필요없이 새 요소를 효율적으로 추가하여 정렬 된 목록을 유지 관리 할 수 ​​있습니다. 방금 데이터 구조 (버킷)를 직접 조작하면됩니다.

Quicksort는 내부 위치가 아니며 정렬 된 목록을 반환하려면 전체 정렬을 실행해야합니다.