QuantAritro_FeasiblyApplicable QuantaFeasibleAritro
QuantaFeasibleAritro
/ gist:748d81641eefaaed80dae18601bd1b44
Created
December 19, 2020 22:15
— forked from andlima/gist:1774060
Median of medians selection algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int find_kth(int *v, int n, int k) { | |
| if (n == 1 && k == 0) return v[0]; | |
| int m = (n + 4)/5; | |
| int *medians = new int[m]; | |
| for (int i=0; i<m; i++) { | |
| if (5*i + 4 < n) { | |
| int *w = v + 5*i; | |
| for (int j0=0; j0<3; j0++) { | |
| int jmin = j0; |