Sıra İstatistikleri / K. Eleman (Order Statistics / Kth Element) Algoritması

1function medianOfMedians(arr: number[], k: number): number {
2  if (arr.length <= 5) {
3    arr.sort((a, b) => a - b);
4    return arr[k];
5  }
6
7  const medians: number[] = [];
8  for (let i = 0; i < arr.length; i += 5) {
9    const group = arr.slice(i, i + 5);
10    group.sort((a, b) => a - b);
11    medians.push(group[Math.floor(group.length / 2)]);
12  }
13
14  const pivot = medianOfMedians(medians, Math.floor(medians.length / 2));
15  
16  const low: number[] = [];
17  const equal: number[] = [];
18  const high: number[] = [];
19
20  for (const num of arr) {
21    if (num < pivot) low.push(num);
22    else if (num === pivot) equal.push(num);
23    else high.push(num);
24  }
25
26  if (k < low.length) {
27    return medianOfMedians(low, k);
28  } else if (k < low.length + equal.length) {
29    return pivot;
30  } else {
31    return medianOfMedians(high, k - low.length - equal.length);
32  }
33}