jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2023, the SerenityOS developers.
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/QuickSelect.h>
10#include <AK/QuickSort.h>
11
12template<typename Collection>
13int naive_select(Collection& a, int k)
14{
15 quick_sort(a);
16 return k;
17}
18
19TEST_CASE(quickselect_inplace)
20{
21
22 // Test the various Quickselect Pivot methods against the naive select
23 Array<int, 64> array;
24 Array<int, 64> naive_results;
25
26 auto reset_array = [&]() {
27 for (size_t i = 0; i < 64; ++i)
28 array[i] = (64 - i) % 32 + 32;
29 };
30
31 // Populate naive results
32 reset_array();
33 for (size_t k = 0; k < 64; ++k) {
34 naive_results[k] = array.at(naive_select(array, k));
35 }
36
37 // Default configuration of `quick_select`
38 reset_array();
39 for (size_t k = 0; k < 64; ++k) {
40 EXPECT(naive_results[k] == array.at(AK::quickselect_inplace(array, k)));
41 }
42
43 // first_element pivot function
44 reset_array();
45 for (size_t k = 0; k < 64; ++k) {
46 EXPECT(naive_results[k] == array.at(AK::quickselect_inplace(array, k, [](auto collection, size_t left, size_t right, auto less_than) { return AK::PivotFunctions::first_element(collection, left, right, less_than); })));
47 }
48
49 // middle_element pivot function
50 reset_array();
51 for (size_t k = 0; k < 64; ++k) {
52 EXPECT(naive_results[k] == array.at(AK::quickselect_inplace(array, k, [](auto collection, size_t left, size_t right, auto less_than) { return AK::PivotFunctions::middle_element(collection, left, right, less_than); })));
53 }
54
55 // random_element pivot function
56 reset_array();
57 for (size_t k = 0; k < 64; ++k) {
58 EXPECT(naive_results[k] == array.at(AK::quickselect_inplace(array, k, [](auto collection, size_t left, size_t right, auto less_than) { return AK::PivotFunctions::random_element(collection, left, right, less_than); })));
59 }
60
61 // median_of_medians pivot function
62 reset_array();
63 for (size_t k = 0; k < 64; ++k) {
64 EXPECT(naive_results[k] == array.at(AK::quickselect_inplace(array, k, [](auto collection, size_t left, size_t right, auto less_than) { return AK::PivotFunctions::median_of_medians(collection, left, right, less_than); })));
65 }
66}