[PR #1550] feat: add quick select algorithm using median of medians #2159

New Issue

claunia · 2026-01-29T15:29:42Z

claunia commented

2026-01-29 15:29:42 +00:00

Original Pull Request: https://github.com/TheAlgorithms/C/pull/1550

State: open
Merged: No

Description of Change

This Pull Request adds the Quick Select algorithm using the median of medians approach. Unlike the standard Quick Select algorithm which has a worst-case time complexity of O(n^2) depending on pivot selection, this implementation uses the median of medians technique to guarantee a "good" pivot. This ensures a worst-case time complexity of O(n), making it highly efficient for finding the kth largest element in an array.

References

Checklist

Added description of change
Added file name matches File name guidelines
Added tests and example, test must pass
Relevant documentation/comments is changed or added
PR title follows semantic commit guidelines
Search previous suggestions before making a new one, as yours may be a duplicate.
I acknowledge that all my contributions will be made under the project's license.

Notes: Implemented a linear-time selection algorithm using median-of-medians for optimal pivot selection and O(n) worst-case performance.

**Original Pull Request:** https://github.com/TheAlgorithms/C/pull/1550 **State:** open **Merged:** No --- #### Description of Change This Pull Request adds the Quick Select algorithm using the median of medians approach. Unlike the standard Quick Select algorithm which has a worst-case time complexity of O(n^2) depending on pivot selection, this implementation uses the median of medians technique to guarantee a "good" pivot. This ensures a worst-case time complexity of O(n), making it highly efficient for finding the kth largest element in an array. #### References #### Checklist - [x] Added description of change - [x] Added file name matches [File name guidelines](https://github.com/TheAlgorithms/C/blob/master/CONTRIBUTING.md#File-Name-guidelines) - [x] Added tests and example, test must pass - [x] Relevant documentation/comments is changed or added - [x] PR title follows semantic [commit guidelines](https://github.com/TheAlgorithms/C/blob/master/CONTRIBUTING.md#Commit-Guidelines) - [x] Search previous suggestions before making a new one, as yours may be a duplicate. - [x] I acknowledge that all my contributions will be made under the project's license. Notes: Implemented a linear-time selection algorithm using median-of-medians for optimal pivot selection and O(n) worst-case performance.

claunia added the pull-request label 2026-01-29 15:29:42 +00:00

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/C#2159