com.sl.algorithms.core.interfaces.select

Interface QuickSelect<T extends java.lang.Comparable>

All Superinterfaces:

BaseInterface<T>, Constants

All Known Subinterfaces:

MedianFinder<T>

All Known Implementing Classes:

BruteForceMedianFinder, PQMedianFinder, QuickSelectMedianFinder, QuickSort

public interface QuickSelect<T extends java.lang.Comparable>
extends BaseInterface<T>

Find kth largest/smallest element in an unsorted array, in Linear time as average-case.

Reference 1
Reference 2
Time : O(N) average case, O(N^2) worst case
Space: O(1)

Field Summary

Fields inherited from interface com.sl.algorithms.core.interfaces.base.Constants

ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET

Method Summary

Modifier and Type	Method and Description
default T	findKthLargest(T[] objects, int k)
default T	findKthSmallest(T[] objects, int k) QuickSelect based default implementation for findKthSmallest problem.
default void	kCheck(int n, int k)
default int	medianOf3(T[] a, int s, int e) Median of 3 strategy
default int	pivotSort(T[] a, int s, int e, int p) Core Algorithm to sort one side of the pivot.
default T	quickSelect(T[] objects, int k, int s, int e) Core QuickSelect Algorithm.

Methods inherited from interface com.sl.algorithms.core.interfaces.base.BaseInterface

checkArray, checkIntArray, checkList

Method Detail

findKthLargest

default T findKthLargest(T[] objects,
                         int k)

findKthSmallest

default T findKthSmallest(T[] objects,
                          int k)

QuickSelect based default implementation for findKthSmallest problem.

Parameters:

objects - input array

k - 3rd smallest = 3, when objects:[1,2,3,4,5] and k=3

Returns:

kth smallest element in objects

quickSelect

default T quickSelect(T[] objects,
                      int k,
                      int s,
                      int e)

Core QuickSelect Algorithm.

Parameters:

objects - input array

k - 3rd smallest = 3, when objects:[1,2,3,4,5] and k=3

s - start index (inclusive)

e - end index (inclusive)

Returns:

kth element

pivotSort

default int pivotSort(T[] a,
                      int s,
                      int e,
                      int p)

Core Algorithm to sort one side of the pivot.

Parameters:

a - input array

s - start index (inclusive)

e - end index (inclusive)

p - initial pivot

Returns:

pivot index after sort

medianOf3

default int medianOf3(T[] a,
                      int s,
                      int e)

Median of 3 strategy

Parameters:

a - input array

s - start index (inclusive)

e - end index (inclusive)

Returns:

median index

kCheck

default void kCheck(int n,
                    int k)