Talk:Median of medians

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Low

This article has been rated as Low-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Are you sure partition code is correct?

 if list[i] < pivotValue
             swap list[storeIndex] and list[i]
             increment storeIndex

What about the value larger than pivotValue. I think one should swap larger value instead of small one. — Preceding unsigned comment added by Jason.zhang2016 (talk • contribs) 18:10, 6 November 2015 (UTC)[reply]

"From this, using induction one can easily show that..." - NOT[edit]

This should be detailed as well in the article. It is NOT that easy to show. Proof of O(n) running time

89.139.175.178 (talk) 10:56, 27 May 2017 (UTC)Raz[reply]

The math is available on the last page of this PDF, and is indeed more complicated than alluded to in the article: http://stellar.mit.edu/S/course/6/sp12/6.046/courseMaterial/topics/topic2/lectureNotes/L01/L01.pdf 73.95.239.9 (talk) 20:47, 18 April 2019 (UTC)[reply]

Article confuses median approximation with median calculation[edit]

The article as it exists now seems to confuse Tukey's Ninther (an approximation algorithm, which is sometimes called Median of Medians) with BPFRT (an exact algorithm, which is also sometimes called Median of Medians), and this results in significant factual inaccuracies!

I believe the algorithm described in some detail is BPFRT (but haven't looked closely), but the prose describes something like Tukey's ninther.

The problem seems to have been introduced by a user without an account named Harish Victory back in June 2017. — Preceding unsigned comment added by 2607:F140:400:A009:CCDC:F5DA:EC00:1830 (talk) 19:47, 13 April 2018 (UTC)[reply]