BFPRT.java

packagecom.thealgorithms.others;

/**
 * The BFPRT (Median of Medians) algorithm implementation.
 * It provides a way to find the k-th smallest element in an unsorted array
 * with an optimal worst-case time complexity of O(n).
 * This algorithm is used to find the k smallest numbers in an array.
 */
publicfinalclassBFPRT {
privateBFPRT() {
 }

/**
 * Returns the k smallest elements from the array using the BFPRT algorithm.
 *
 * @param arr the input array
 * @param k the number of smallest elements to return
 * @return an array containing the k smallest elements, or null if k is invalid
 */
publicstaticint[] getMinKNumsByBFPRT(int[] arr, intk) {
if (k < 1 || k > arr.length) {
returnnull;
 }
intminKth = getMinKthByBFPRT(arr, k);
int[] res = newint[k];
intindex = 0;
for (intvalue : arr) {
if (value < minKth) {
res[index++] = value;
 }
 }
for (; index != res.length; index++) {
res[index] = minKth;
 }
returnres;
 }

/**
 * Returns the k-th smallest element from the array using the BFPRT algorithm.
 *
 * @param arr the input array
 * @param k the rank of the smallest element to find
 * @return the k-th smallest element
 */
publicstaticintgetMinKthByBFPRT(int[] arr, intk) {
int[] copyArr = copyArray(arr);
returnbfprt(copyArr, 0, copyArr.length - 1, k - 1);
 }

/**
 * Creates a copy of the input array.
 *
 * @param arr the input array
 * @return a copy of the array
 */
publicstaticint[] copyArray(int[] arr) {
int[] copyArr = newint[arr.length];
System.arraycopy(arr, 0, copyArr, 0, arr.length);
returncopyArr;
 }

/**
 * BFPRT recursive method to find the k-th smallest element.
 *
 * @param arr the input array
 * @param begin the starting index
 * @param end the ending index
 * @param i the index of the desired smallest element
 * @return the k-th smallest element
 */
publicstaticintbfprt(int[] arr, intbegin, intend, inti) {
if (begin == end) {
returnarr[begin];
 }
intpivot = medianOfMedians(arr, begin, end);
int[] pivotRange = partition(arr, begin, end, pivot);
if (i >= pivotRange[0] && i <= pivotRange[1]) {
returnarr[i];
 } elseif (i < pivotRange[0]) {
returnbfprt(arr, begin, pivotRange[0] - 1, i);
 } else {
returnbfprt(arr, pivotRange[1] + 1, end, i);
 }
 }

/**
 * Finds the median of medians as the pivot element.
 *
 * @param arr the input array
 * @param begin the starting index
 * @param end the ending index
 * @return the median of medians
 */
publicstaticintmedianOfMedians(int[] arr, intbegin, intend) {
intnum = end - begin + 1;
intoffset = num % 5 == 0 ? 0 : 1;
int[] mArr = newint[num / 5 + offset];
for (inti = 0; i < mArr.length; i++) {
mArr[i] = getMedian(arr, begin + i * 5, Math.min(end, begin + i * 5 + 4));
 }
returnbfprt(mArr, 0, mArr.length - 1, mArr.length / 2);
 }

/**
 * Partitions the array around a pivot.
 *
 * @param arr the input array
 * @param begin the starting index
 * @param end the ending index
 * @param num the pivot element
 * @return the range where the pivot is located
 */
publicstaticint[] partition(int[] arr, intbegin, intend, intnum) {
intsmall = begin - 1;
intcur = begin;
intbig = end + 1;
while (cur != big) {
if (arr[cur] < num) {
swap(arr, ++small, cur++);
 } elseif (arr[cur] > num) {
swap(arr, --big, cur);
 } else {
cur++;
 }
 }
returnnewint[] {small + 1, big - 1};
 }

/**
 * Finds the median of the elements between the specified range.
 *
 * @param arr the input array
 * @param begin the starting index
 * @param end the ending index
 * @return the median of the specified range
 */
publicstaticintgetMedian(int[] arr, intbegin, intend) {
insertionSort(arr, begin, end);
intsum = begin + end;
intmid = sum / 2 + (sum % 2);
returnarr[mid];
 }

/**
 * Sorts a portion of the array using insertion sort.
 *
 * @param arr the input array
 * @param begin the starting index
 * @param end the ending index
 */
publicstaticvoidinsertionSort(int[] arr, intbegin, intend) {
if (arr == null || arr.length < 2) {
return;
 }
for (inti = begin + 1; i != end + 1; i++) {
for (intj = i; j != begin; j--) {
if (arr[j - 1] > arr[j]) {
swap(arr, j - 1, j);
 } else {
break;
 }
 }
 }
 }

/**
 * Swaps two elements in an array.
 *
 * @param arr the input array
 * @param i the index of the first element
 * @param j the index of the second element
 */
publicstaticvoidswap(int[] arr, inti, intj) {
inttemp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
 }
}