algorithm-examples/cpp-algorithm/src/search/quick_select.h at main · codejsha/algorithm-examples · GitHub

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#ifndef CPP_ALGORITHM_QUICK_SELECT_H
#define CPP_ALGORITHM_QUICK_SELECT_H

#include <vector>

namespace QuickSelect
{
    /**
     * \brief Find the k-th smallest element in an array.
     * \param array an array of integers
     * \param k the k-th smallest
     * \return the k-th smallest element
     */
    int FindKthSmallestElement(
        std::vector<int>& array,
        int k);

    /**
     * \brief Find the k-th smallest element in an array.
     * \param array an array of integers
     * \param k the k-th smallest
     * \return the k-th smallest element
     */
    int FindKthLargestElement(
        std::vector<int>& array,
        int k);

    /**
     * \brief QuickSelect is an algorithm used to select the k-th smallest (or largest) element in an unordered list of
     * elements.
     * \details It is a variation of QuickSort algorithm and works by partitioning the list into two sub lists around a
     * pivot element, with elements less than or equal to the pivot on one side and elements greater than the pivot on
     * the other.
     * \param array the array to search
     * \param left the left index of the array
     * \param right the right index of the array
     * \param k the index of the k-th element
     * \return the k-th element in the array
     */
    int QuickSelectAlgorithm(
        std::vector<int>& array,
        int left,
        int right,
        int k);
}

// ----------------------------------------------------------------------------
/**
 * \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
 */
inline int Partition(
    std::vector<int>& array,
    const int left,
    const int right)
{
    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;
}

// ----------------------------------------------------------------------------
inline int QuickSelect::QuickSelectAlgorithm(
    std::vector<int>& array,
    const int left,
    const int right,
    const int k)
{
    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);
}

// ----------------------------------------------------------------------------
inline int QuickSelect::FindKthSmallestElement(
    std::vector<int>& array,
    const int k)
{
    constexpr int left = 0;
    const int right = static_cast<int>(array.size()) - 1;
    return QuickSelectAlgorithm(array, left, right, k - 1);
}

// ----------------------------------------------------------------------------
inline int QuickSelect::FindKthLargestElement(
    std::vector<int>& array,
    int k)
{
    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);
}

#endif