Forked from LeeYeeze/QuickSelect median of medians.js
Last active
September 5, 2021 01:37
-
-
Save wlchn/ee15de1da59b8d6981a400eee4376ea4 to your computer and use it in GitHub Desktop.
Median of medians javascript - find median in an unsorted array, worst-case complexity O(n).
This file contains 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
// Median of medians: https://en.wikipedia.org/wiki/Median_of_medians | |
// find median in an unsorted array, worst-case complexity O(n). | |
export const selectMedian = (arr, compare) => { | |
return selectK(arr, Math.floor(arr.length / 2), compare); | |
}; | |
export const selectK = (arr, k, compare) => { | |
if (!Array.isArray(arr) || arr.length === 0 || arr.length - 1 < k) { | |
return; | |
} | |
if (arr.length === 1) { | |
return arr[0]; | |
} | |
let idx = selectIdx(arr, 0, arr.length - 1, k, compare || defaultCompare); | |
return arr[idx]; | |
}; | |
const partition = (arr, left, right, pivot, compare) => { | |
let temp = arr[pivot]; | |
arr[pivot] = arr[right]; | |
arr[right] = temp; | |
let track = left; | |
for (let i = left; i < right; i++) { | |
// if (arr[i] < arr[right]) { | |
if (compare(arr[i], arr[right]) === -1) { | |
let t = arr[i]; | |
arr[i] = arr[track]; | |
arr[track] = t; | |
track++; | |
} | |
} | |
temp = arr[track]; | |
arr[track] = arr[right]; | |
arr[right] = temp; | |
return track; | |
}; | |
const selectIdx = (arr, left, right, k, compare) => { | |
if (left === right) { | |
// return arr[left]; | |
return left; | |
} | |
let dest = left + k; | |
while (true) { | |
let pivotIndex = | |
right - left + 1 <= 5 | |
? Math.floor(Math.random() * (right - left + 1)) + left | |
: medianOfMedians(arr, left, right, compare); | |
pivotIndex = partition(arr, left, right, pivotIndex, compare); | |
if (pivotIndex === dest) { | |
return pivotIndex; | |
} else if (pivotIndex < dest) { | |
left = pivotIndex + 1; | |
} else { | |
right = pivotIndex - 1; | |
} | |
} | |
}; | |
const medianOfMedians = (arr, left, right, compare) => { | |
let numMedians = Math.ceil((right - left) / 5); | |
for (let i = 0; i < numMedians; i++) { | |
let subLeft = left + i * 5; | |
let subRight = subLeft + 4; | |
if (subRight > right) { | |
subRight = right; | |
} | |
let medianIdx = selectIdx(arr, subLeft, subRight, Math.floor((subRight - subLeft) / 2), compare); | |
let temp = arr[medianIdx]; | |
arr[medianIdx] = arr[left + i]; | |
arr[left + i] = temp; | |
} | |
return selectIdx(arr, left, left + numMedians - 1, Math.floor(numMedians / 2), compare); | |
}; | |
const defaultCompare = (a, b) => { | |
return a < b ? -1 : a > b ? 1 : 0; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment