quicksort 구현을위한 자바 median의 중간 값을 찾는 방법

Question

그래서 밤새 숙제를위한 퀵 소트 알고리즘을 구현하고 두 시간 동안 검색 한 후에 중간 값의 구체적인 구현을 찾을 수 없었습니다 파티셔닝. 그래서, 나는 내 알고리즘의 어떤 부분이 끔찍하게 부서 졌는지, 그리고 모든 온라인 알고리즘은 의사 코드 (의사 결정에 대한 설명이 너무나 모호하다) 때문에, 막대한 장애물에 갇혀있다. 내 구현에 대해 확인하겠습니다. 그래서 여기 내 프랑켄슈타인 코드 median 피벗 선택의 중간 어떻게 자바에서 quicksort 함께 작동하는 문서 후 문서를 읽은 후입니다.

http://mitpress.mit.edu/algorithms/solutions/chap9-solutions.pdf : 여기

내가 지금까지 심지어 원격으로 도움이 발견 한 유일한 원천이며, 그들은 모든 알고리즘 작업을 구성하는 부품에 고통스럽게 모호한, 의도적으로 그렇게 많은 시간 검색을 보낸 이후 보인다

http://www.cs.umd.edu/~meesh/351/mount/lectures/lect9-medians-selection.pdf

* HTTP : //www.ics.uci.edu/~eppstein/161/960130.html

* HTTP : //en.wikipedia.org/wiki/Selection_algorithm

여기

내 퀵 알고리즘 :

{Removed Code} 

그리고 여기 내 선택 방법, 나는 내가 중간 값을 선택하고 중간 값의 평균 어떻게 끔찍하게 엉망 부분은 생각하지만, 나는 온라인 아무것도 찾을 수 없습니다 파티션에 저를 안내하는 것은 : 내가했다 아무것도 다른 사람이 있다면

또한 내 일반 퀵 파티션 방법을 사용하지만, 피벗 매개 변수로 제공되도록 약간 변경 내 분할에 대한

{Removed Code} 

, 나도 몰라 모든 소스가 온라인이기 때문에해야 할 일은이 영역에서도 모호합니다. 여기

{Removed Code} 

는 경우, 5의 그룹을 정렬 내 삽입 정렬이다 :

{Removed Code} 

내가 망쳐 알고리즘의 어떤 부분에 어떤 통찰력은 대단히 봤는데으로 감상 할 수있다 뭐가 잘못 됐는지를 찾으려고 벽에 머리를 두드리는 소리. 내 JUnit 테스트가 [1..100]의 사전 정렬 된 배열에 대해 예상 결과가 50 인 중앙값을 선택하지 못했기 때문에 선택 알고리즘에 큰 실수가있었습니다. 그러나 알고리즘은 항상 54를 울립니다.

Answer 1

옆에있는 요소를 선택하는 5 개의 요소 인 "하위 집합"에서 중앙값을 선택해야합니다. 중간 값은 2의 인덱스를 가지지 만 인덱스 3을 선택합니다. 값에 : 당신은 필요 : (20)에 의해 5의 표에서 숫자를 쓰기

int median = subset[2]; // Or sslength/2 if you don't like hardcoded values 

그런데, "중간 값의 중앙값은"[1..100]의 48 것 또는 (53),하지 (50) 중간 행 (3,8,13, ...)은 "부분 집합"의 중간 값입니다.