Quickselect algorithm implementation and its time-complexity

Question

I wrote this code to find kth smallest element in the array by renowned algorithm quickselect. Here is the link where you can see the working code.

1. What points are there to be improved? Could you please leave your valuable comments?
2. I tested its time complexity by countFindElement and countPartition together. It is always at most O(2n). But I don't understand why it doesn't yield O(n²). Could you please explain it?

using System.Text.Json;

int []arr = {13,9,8,3,3,4,6,11,3,5};
//int []arr = {157, 38, 97, 17, 148, 23, 108, 111, 1, 196, 74, 4, 40, 143, 119, 108, 15, 169, 108, 157, 58, 87, 135, 14, 127, 132, 141, 124, 142, 34, 142, 141, 113, 86, 86, 153, 125, 150, 160, 194, 182, 57, 189, 180, 18, 192, 111, 150, 123, 88, 192, 126, 13, 97, 200, 188, 96, 85, 168, 23, 60, 3, 56, 168, 130, 169, 161, 20, 160, 63, 90, 5, 52, 85, 90, 139, 125, 119, 109, 112, 73, 40, 85, 62, 177, 160, 194, 128, 184, 102, 123, 87, 20, 52, 184, 17, 102, 193, 67, 169};
//int[] arr = { 158, 481, 313, 277, 16, 495, 94, 109, 272, 255, 374, 9, 79, 205, 179, 386, 242, 315, 223, 250, 465, 257, 289, 405, 347, 390, 496, 386, 430, 121, 352, 75, 251, 376, 169, 492, 355, 341, 208, 391, 171, 382, 331, 471, 358, 478, 25, 336, 304, 84, 487, 178, 258, 3, 410, 324, 180, 468, 275, 456, 97, 407, 433, 441, 176, 148, 350, 121, 275, 461, 122, 350, 180, 337, 494, 284, 414, 352, 52, 89, 464, 105, 94, 328, 306, 404, 457, 325, 10, 346, 177, 276, 68, 250, 440, 266, 163, 233, 191, 412, 291, 198, 320, 171, 141, 243, 278, 399, 205, 77, 342, 402, 53, 456, 374, 36, 389, 293, 453, 458, 25, 56, 40, 127, 278, 330, 93, 250, 185, 293, 243, 22, 377, 0, 217, 171, 130, 308, 365, 440, 175, 9, 493, 283, 264, 63, 365, 485, 429, 353, 479, 286, 190, 290, 25, 336, 203, 462, 236, 340, 279, 311, 118, 449, 357, 93, 139, 471, 393, 279, 88, 51, 280, 446, 368, 330, 390, 10, 494, 388, 406, 33, 420, 86, 236, 109, 183, 247, 157, 154, 462, 215, 40, 428, 374, 330, 85, 263, 363, 224, 143, 43, 394, 15, 431, 355, 1, 225, 246, 249, 430, 151, 68, 432, 284, 294, 442, 126, 216, 416, 500, 377, 440, 416, 169, 310, 15, 417, 178, 136, 411, 127, 77, 358, 460, 146, 409, 357, 341, 497, 151, 255, 245, 306, 342, 257, 119, 302, 386, 278, 124, 493, 315, 491, 150, 174, 204, 85, 97, 240, 240, 240, 382, 173, 3, 166, 460, 413, 65, 122, 275, 183, 144, 142, 344, 283, 366, 129, 107, 98, 410, 282, 228, 465, 39, 455, 144, 2, 139, 444, 407, 154, 132, 376, 385, 348, 30, 213, 366, 72, 227, 243, 496, 57, 315, 420, 257, 244, 187, 194, 60, 365, 345, 389, 286, 424, 493, 188, 270, 423, 16, 336, 228, 196, 355, 427, 288, 109, 124, 200, 143, 248, 219, 343, 203, 347, 345, 469, 327, 128, 481, 16, 357, 110, 37, 447, 417, 107, 489, 468, 490, 434, 86, 383, 245, 159, 472, 382, 1, 251, 268, 354, 49, 138, 124, 275, 184, 172, 499, 133, 150, 177, 381, 306, 122, 232, 77, 64, 186, 105, 363, 486, 209, 213, 351, 285, 420, 148, 499, 448, 438, 131, 469, 239, 446, 440, 484, 455, 81, 68};

Console.WriteLine(JsonSerializer.Serialize(arr));
for (int i = 0; i < arr.Length + 1; ++i)
{
    Console.WriteLine($"{i + 1} smallest => " + FindKthElem(arr, i + 1));
}

/*
 2) How is it NOT "O(n^2)"? It is almost "O(2n)"? How?
 
 It finds k-th smallest element(k) in the given array, arr
 l left index
 r right index
 */
int FindKthElem(int[] arr, int k)
{
    int countFindElement = 0;
    int countPartition = 0;
    if (k > arr.Length) return -1;
    int r = arr.Length - 1;
    int l = 0;
    while (l <= r)
    {
        countFindElement++;
        // O(n)
        int pivotIndex = Partition(arr, l, r, out countPartition);
        countFindElement += countPartition;
        int nthElement = arr[pivotIndex];
        if (k - 1 == pivotIndex)
        {
            Console.WriteLine("how many " + countFindElement);
            return nthElement;
        }
        else if (k - 1 > pivotIndex)
        {
            l = pivotIndex + 1;
        }
        else
        {
            r = pivotIndex - 1;
        }
    }
    Console.WriteLine("how many " + countFindElement);
    return -1;
}

/*
 1) It is haore partition -- Isn't it?
 
 I hide pivot element always at rightmost.
 It places smaller or equal elements than pivot to that of left-side
 It places greater elements than pivot to that of right-side
 */
int Partition(int[] a, int l, int r, out int count)
{
    int c = 0;
    int pIndex = r;
    int p = a[pIndex];
    r--;
    while(l <= r)
    {
        c++;
        while (l < pIndex && a[l] <= p)
        {
            l++;
        }
        while (r >= 0 && a[r] > p)
        {
            r--;
        }

        if (l < r)
        {
            (a[l], a[r]) = (a[r], a[l]);
            l++;
            r--;
        }
    }
    (a[l], a[pIndex]) = (a[pIndex], a[l]);
    count = c;
    return l;
}

The output

[13,9,8,3,3,4,6,11,3,5]
how many 10
1 smallest => 3
how many 12
2 smallest => 3
how many 12
3 smallest => 3
how many 12
4 smallest => 4
how many 12
5 smallest => 5
how many 10
6 smallest => 6
how many 8
7 smallest => 8
how many 6
8 smallest => 9
how many 4
9 smallest => 11
how many 2
10 smallest => 13
11 smallest => -1

Answer 1

int []arr = {13,9,8,3,3,4,6,11,3,5};

• Naming an array to arr is not really helping the reader/maintainer of the codebase
• Try to express your intent with the variable name, like inputDataSet, unorderedElements, etc.

---

for (int i = 0; i < arr.Length + 1; ++i)
{
    Console.WriteLine($"{i + 1} smallest => " + FindKthElem(arr, i + 1));
}

• In both places where you refer to i you are using i + 1
  • Start the iteration from 1 in this case instead of 0
• Mixing string concatenation and string interpolation is a suboptimal
  • Prefer to use string interpolation instead

for (int i = 1; i < arr.Length; i++)
{
    Console.WriteLine($"{i} smallest => {FindKthElem(arr, i)}");
}

---

int countFindElement = 0;
int countPartition = 0;
if (k > arr.Length) return -1;

• If you have early exit statements then please do them before any other statement
  • You have allocated two variables which is not used if you early exit

---

int r = arr.Length - 1;
int l = 0;

• Yet again, try to use better naming
  • like the ones that you have mentioned in the comment section

---

int pivotIndex = Partition(arr, l, r, out countPartition);

• I would suggest to return with a named ValueTuple instead
• Also please try to follow one of the naming conventions of C#
  • Method names usually start with a verb

---

int nthElement = arr[pivotIndex];

• The method name is find the Kth element but you have named the result to Nth element
  • Please try to be more consistent with naming

---

int Partition(int[] a, int l, int r, out int count)

• Please try to avoid naming parameters/fields/variables with a single letter
  • The only exception is the loop variable

---

while (l < pIndex && a[l] <= p)
{
    l++;
}

• IMHO it would much easier if you would calculate the increment value and use a simple += without a while loop
  • The same is true for the r new value calculation

---

(a[l], a[r]) = (a[r], a[l]);
...
(a[l], a[pIndex]) = (a[pIndex], a[l]);

• Are you aware of the fact that you are modifying an input parameter?

Answer 2

I'm a bit of a fan of making code as reusable and adaptable to different situations as possible, so I would like to introduce you to generics:

T FindKthElem(T[] arr, int k) where T : IComparable<T>

...

int Partition(T[] a, int l, int r, out int count) where T : IComparable<T>

...

    while (l < pIndex && a[l].CompareTo(p) <= 0)
    {
        l++;
    }
    while (r >= 0 && a[r].CompareTo(p) > 0)
    {
        r--;
    }

What this gives you is a way to have arrays of any data type as long as they implement an interface known as IComparable<T>, which int does, for example. So does long, double, decimal and string, for that matter.