[FEATURE REQUEST] Add Deterministic QuickSelect (Median of Medians) algorithm in divideandconquer package

[lukmanu1]

What would you like to Propose?

Proposal

I would like to add a deterministic QuickSelect algorithm using the Median of Medians method under the divideandconquer package.

This algorithm finds the kth smallest element in an unsorted array in O(n) worst-case time complexity by using a well-balanced pivot selection strategy. It follows the divide-and-conquer paradigm and ensures deterministic performance compared to the randomized QuickSelect version.

Purpose

Adding this algorithm will:

• Enrich the divideandconquer package with a deterministic selection algorithm.
• Help learners compare deterministic and randomized approaches.
• Maintain consistency with the repository’s focus on educational, well-documented algorithms.

Implementation

• Fully static and final class
• Proper JavaDoc documentation
• Unit tests using JUnit 5
• Follows the project’s CheckStyle and conventions

Reference

Median of Medians - Wikipedia
MIT - Youtube Channel

Please assign this issue to me as part of my Hacktoberfest contribution.

Issue details

Algorithm Name

Deterministic QuickSelect (Median of Medians)

Problem Statement

Find the kth smallest element in an unsorted array in O(n) worst-case time complexity. The algorithm uses the Median of Medians method to select a pivot in a well-balanced way, ensuring deterministic performance, unlike the randomized QuickSelect.

Algorithm Description

The algorithm follows the divide-and-conquer paradigm:

1. Divide the array into groups of 5 elements.
2. Find the median of each group.
3. Recursively find the median of these medians — this becomes the pivot.
4. Partition the array around the pivot and recursively select in the correct partition.

Benefits

• Guarantees O(n) worst-case performance.
• Educational: allows learners to compare deterministic vs randomized selection.
• Enhances the divideandconquer package with a well-documented, unit-tested algorithm.

Implementation Details

• Class will be static and final.
• Full JavaDoc documentation included.
• Unit tests written using JUnit 5.
• Follows the project’s CheckStyle and conventions.

Reference

Median of Medians - Wikipedia
MIT - Youtube Channel

This issue is intended for Hacktoberfest, please assign it to me.

Additional Information

No response