-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquick_select.cpp
More file actions
67 lines (61 loc) · 2.1 KB
/
quick_select.cpp
File metadata and controls
67 lines (61 loc) · 2.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include "quick_select.h"
/**
* \brief Partition the array around the pivot element.
* \details To find the k-th smallest (or largest) element, partition the array into two sub lists.
* Elements less than or equal to the pivot are on one side, and elements greater than the pivot are on the other side.
* \param array the array to partition
* \param left the left index of the array
* \param right the right index of the array
* \return the index of the pivot element
* \note
* Comparison Explanation:
* - Finding k-th smallest element: This comparison is used to find the k-th smallest element:
* \code if (arr[j] <= pivot) \endcode
* - Finding k-th largest element: This comparison is used to find the k-th largest element:
* \code if (arr[j] >= pivot) \endcode
*/
auto Partition(std::vector<int>& array, const int left, const int right) -> int
{
const int pivot = array[right];
int i = left - 1;
for (int j = left; j < right; ++j)
{
if (array[j] <= pivot)
{
++i;
std::swap(array[i], array[j]);
}
}
std::swap(array[i + 1], array[right]);
return i + 1;
}
auto QuickSelect::QuickSelectAlgorithm(std::vector<int>& array, const int left, const int right, const int k) -> int
{
if (left == right)
{
return array[left];
}
const int pivot_index = Partition(array, left, right);
if (k == pivot_index)
{
return array[pivot_index];
}
if (k < pivot_index)
{
return QuickSelectAlgorithm(array, left, pivot_index - 1, k);
}
return QuickSelectAlgorithm(array, pivot_index + 1, right, k);
}
auto QuickSelect::FindKthSmallestElement(std::vector<int>& array, const int k) -> int
{
constexpr int left = 0;
const int right = static_cast<int>(array.size()) - 1;
return QuickSelectAlgorithm(array, left, right, k - 1);
}
auto QuickSelect::FindKthLargestElement(std::vector<int>& array, int k) -> int
{
constexpr int left = 0;
const int right = static_cast<int>(array.size()) - 1;
k = static_cast<int>(array.size()) - k;
return QuickSelectAlgorithm(array, left, right, k);
}