QuickSelectTest.java

packagecom.thealgorithms.searches;

importstaticorg.junit.jupiter.api.Assertions.*;

importjava.util.*;
importjava.util.stream.Collectors;
importorg.junit.jupiter.api.Test;

classQuickSelectTest {

@Test
voidquickSelectMinimumOfOneElement() {
List<Integer> elements = Collections.singletonList(42);
intminimum = QuickSelect.select(elements, 0);
assertEquals(42, minimum);
 }

@Test
voidquickSelectMinimumOfTwoElements() {
List<Integer> elements1 = Arrays.asList(42, 90);
List<Integer> elements2 = Arrays.asList(90, 42);

intminimum1 = QuickSelect.select(elements1, 0);
intminimum2 = QuickSelect.select(elements2, 0);

assertEquals(42, minimum1);
assertEquals(42, minimum2);
 }

@Test
voidquickSelectMinimumOfThreeElements() {
List<Integer> elements1 = Arrays.asList(1, 2, 3);
List<Integer> elements2 = Arrays.asList(2, 1, 3);
List<Integer> elements3 = Arrays.asList(2, 3, 1);

intminimum1 = QuickSelect.select(elements1, 0);
intminimum2 = QuickSelect.select(elements2, 0);
intminimum3 = QuickSelect.select(elements3, 0);

assertEquals(1, minimum1);
assertEquals(1, minimum2);
assertEquals(1, minimum3);
 }

@Test
voidquickSelectMinimumOfManyElements() {
List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
intactual = QuickSelect.select(elements, 0);
intexpected = elements.stream().min(Comparator.naturalOrder()).get();
assertEquals(expected, actual);
 }

@Test
voidquickSelectMaximumOfOneElement() {
List<Integer> elements = Collections.singletonList(42);
intmaximum = QuickSelect.select(elements, 0);
assertEquals(42, maximum);
 }

@Test
voidquickSelectMaximumOfTwoElements() {
List<Integer> elements1 = Arrays.asList(42, 90);
List<Integer> elements2 = Arrays.asList(90, 42);

intmaximum1 = QuickSelect.select(elements1, 1);
intmaximum2 = QuickSelect.select(elements2, 1);

assertEquals(90, maximum1);
assertEquals(90, maximum2);
 }

@Test
voidquickSelectMaximumOfThreeElements() {
List<Integer> elements1 = Arrays.asList(1, 2, 3);
List<Integer> elements2 = Arrays.asList(2, 1, 3);
List<Integer> elements3 = Arrays.asList(2, 3, 1);

intmaximum1 = QuickSelect.select(elements1, 2);
intmaximum2 = QuickSelect.select(elements2, 2);
intmaximum3 = QuickSelect.select(elements3, 2);

assertEquals(3, maximum1);
assertEquals(3, maximum2);
assertEquals(3, maximum3);
 }

@Test
voidquickSelectMaximumOfManyElements() {
List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
intactual = QuickSelect.select(elements, NUM_RND_ELEMENTS - 1);
intexpected = elements.stream().max(Comparator.naturalOrder()).get();
assertEquals(expected, actual);
 }

@Test
voidquickSelectMedianOfOneElement() {
List<Integer> elements = Collections.singletonList(42);
intmedian = QuickSelect.select(elements, 0);
assertEquals(42, median);
 }

@Test
voidquickSelectMedianOfThreeElements() {
List<Integer> elements1 = Arrays.asList(1, 2, 3);
List<Integer> elements2 = Arrays.asList(2, 1, 3);
List<Integer> elements3 = Arrays.asList(2, 3, 1);

intmedian1 = QuickSelect.select(elements1, 1);
intmedian2 = QuickSelect.select(elements2, 1);
intmedian3 = QuickSelect.select(elements3, 1);

assertEquals(2, median1);
assertEquals(2, median2);
assertEquals(2, median3);
 }

@Test
voidquickSelectMedianOfManyElements() {
intmedianIndex = NUM_RND_ELEMENTS / 2;
List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
intactual = QuickSelect.select(elements, medianIndex);

List<Integer> elementsSorted = getSortedCopyOfList(elements);
assertEquals(elementsSorted.get(medianIndex), actual);
 }

@Test
voidquickSelect30thPercentileOf10Elements() {
List<Integer> elements = generateRandomIntegers(10);
intactual = QuickSelect.select(elements, 2);

List<Integer> elementsSorted = getSortedCopyOfList(elements);
assertEquals(elementsSorted.get(2), actual);
 }

@Test
voidquickSelect30thPercentileOfManyElements() {
intpercentile30th = NUM_RND_ELEMENTS / 10 * 3;
List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
intactual = QuickSelect.select(elements, percentile30th);

List<Integer> elementsSorted = getSortedCopyOfList(elements);
assertEquals(elementsSorted.get(percentile30th), actual);
 }

@Test
voidquickSelect70thPercentileOf10Elements() {
List<Integer> elements = generateRandomIntegers(10);
intactual = QuickSelect.select(elements, 6);

List<Integer> elementsSorted = getSortedCopyOfList(elements);
assertEquals(elementsSorted.get(6), actual);
 }

@Test
voidquickSelect70thPercentileOfManyElements() {
intpercentile70th = NUM_RND_ELEMENTS / 10 * 7;
List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
intactual = QuickSelect.select(elements, percentile70th);

List<Integer> elementsSorted = getSortedCopyOfList(elements);
assertEquals(elementsSorted.get(percentile70th), actual);
 }

@Test
voidquickSelectMedianOfThreeCharacters() {
List<Character> elements = Arrays.asList('X', 'Z', 'Y');
charactual = QuickSelect.select(elements, 1);
assertEquals(actual, 'Y');
 }

@Test
voidquickSelectMedianOfManyCharacters() {
List<Character> elements = generateRandomCharacters(NUM_RND_ELEMENTS);
charactual = QuickSelect.select(elements, NUM_RND_ELEMENTS / 30);

List<Character> elementsSorted = getSortedCopyOfList(elements);
assertEquals(elementsSorted.get(NUM_RND_ELEMENTS / 30), actual);
 }

@Test
voidquickSelectNullList() {
NullPointerExceptionexception = assertThrows(NullPointerException.class, () -> QuickSelect.select(null, 0));
StringexpectedMsg = "The list of elements must not be null.";
assertEquals(expectedMsg, exception.getMessage());
 }

@Test
voidquickSelectEmptyList() {
List<String> objects = Collections.emptyList();
IllegalArgumentExceptionexception = assertThrows(IllegalArgumentException.class, () -> QuickSelect.select(objects, 0));
StringexpectedMsg = "The list of elements must not be empty.";
assertEquals(expectedMsg, exception.getMessage());
 }

@Test
voidquickSelectIndexOutOfLeftBound() {
IndexOutOfBoundsExceptionexception = assertThrows(IndexOutOfBoundsException.class, () -> QuickSelect.select(Collections.singletonList(1), -1));
StringexpectedMsg = "The index must not be negative.";
assertEquals(expectedMsg, exception.getMessage());
 }

@Test
voidquickSelectIndexOutOfRightBound() {
IndexOutOfBoundsExceptionexception = assertThrows(IndexOutOfBoundsException.class, () -> QuickSelect.select(Collections.singletonList(1), 1));
StringexpectedMsg = "The index must be less than the number of elements.";
assertEquals(expectedMsg, exception.getMessage());
 }

privatestaticfinalintNUM_RND_ELEMENTS = 99;
privatestaticfinalRandomRANDOM = newRandom(42);
privatestaticfinalintASCII_A = 0x41;
privatestaticfinalintASCII_Z = 0x5A;

privatestaticList<Integer> generateRandomIntegers(intn) {
returnRANDOM.ints(n).boxed().collect(Collectors.toList());
 }

privatestaticList<Character> generateRandomCharacters(intn) {
returnRANDOM.ints(n, ASCII_A, ASCII_Z).mapToObj(i -> (char) i).collect(Collectors.toList());
 }

privatestatic <TextendsComparable<T>> List<T> getSortedCopyOfList(List<T> list) {
returnlist.stream().sorted().collect(Collectors.toList());
 }
}