중간 값 알고리즘의 빠른 정렬 작업을하고 있습니다. 나는 일반적으로 선택 정렬을 사용하여 5 개 요소의 하위 배열의 중앙값을 구합니다. 그러나, 수천 개의 서브 어레이가 있다면, 이것은 내가 천 개의 중간 값의 중간 값을 찾아야한다는 것을 의미합니다. 최적의 선택이 아니기 때문에 중간 값을 찾기 위해 선택 정렬을 사용할 수 없다고 생각합니다.quicksort의 중간 값 찾기
질문 :이
사람이 나에게 그 중간을 찾을 수있는 더 좋은 방법을 제안 할 수 있습니까? 미리 감사드립니다.
median-of-medians 알고리즘은 크기 5의 각 블록의 중앙값을 찾은 다음 정렬 알고리즘을 실행하여 중앙값을 찾습니다. 대신 일반적으로 각 블록을 정렬하고 각 블록의 중앙값을 취한 다음 이러한 중간 값에 대한 중간 값의 중간 알고리즘을 재귀 적으로 호출하여 좋은 피벗을 얻습니다. median-of-median 알고리즘의 O (n) 런타임의 상수 요인이 너무 커서 성능이 현저히 떨어지는 경향이 있기 때문에 quicksort에서 median-of-medians 알고리즘을 사용하는 것은 매우 드뭅니다.
원본 접근 방식을 시도해 볼 수있는 몇 가지 가능한 개선 사항이 있습니다. 좋은 피벗을 얻는 가장 간단한 방법은 무작위 요소를 선택하는 것입니다. 그러면 매우 높은 확률로 Θ (n log n) 런타임이됩니다. 무작위성을 사용하는 것이 편하지 않은 경우을 사용해보십시오. 중앙값 중 심의 알고리즘을 수정하면 좋은 피벗 일 수있는 요소를 추측하여 상수 요소를 낮추고 재귀를 차단합니다. 발견되면 일찍. 또한 quicksort를 사용하는 introsort를 작성해 볼 수도 있습니다. 알고리즘이 퇴행하는 것으로 보일 경우 다른 알고리즘 (일반적으로 heapsort)으로 전환합니다.
희망이 도움이됩니다.
도와 주셔서 감사합니다. 빠른 정렬을 최적화하기 위해 median-of-medians 알고리즘을 사용하는 것이 더 좋을 것이라고 생각했습니다. –
중복 : http://stackoverflow.com/questions/480960/code-to-calculate-median-of-five-in-c-sharp – Billiska
@ Billiska-이 질문에 대해 묻는 질문에 대해 생각하지 않습니다. 다섯 요소의 중앙값. 그 대신, OP는 크기 중앙값 알고리즘을 사용합니다.이 알고리즘은 서브 루틴으로 크기가 5 인 블록의 중앙값을 찾아야하지만 꽤 다른 알고리즘입니다. – templatetypedef