Messages in this thread | | | Subject | Re: [PATCH v2] platform/chrome: sensorhub: Implement quickselect for median calculation | From | patchwork-bot+chrome-platform@kernel ... | Date | Mon, 13 Nov 2023 04:50:25 +0000 |
| |
Hello:
This patch was applied to chrome-platform/linux.git (for-kernelci) by Tzung-Bi Shih <tzungbi@kernel.org>:
On Sat, 11 Nov 2023 00:53:14 +0800 you wrote: > The cros_ec_sensor_ring_median function currently uses an inefficient > sorting algorithm (> O(n)) to find the median of an array. This patch > replaces the sorting approach with the quickselect algorithm, which > achieves an average time complexity of O(n). > > The algorithm employs the median-of-three rule to select the pivot, > mitigating worst-case scenarios and reducing the expected number of > necessary comparisons. This strategy enhances the algorithm's > efficiency and ensures a more balanced partitioning. > > [...]
Here is the summary with links: - [v2] platform/chrome: sensorhub: Implement quickselect for median calculation https://git.kernel.org/chrome-platform/c/d131f1f3b459
You are awesome, thank you! -- Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html
| |