# Quickselect algorithm implementation and its time-complexity

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.

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 ## 2 Answers 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#

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?
• Thank you for your ideas. You are absolutely right considering all points. For the last one, yes I'm aware. But what about complexity written in my question and comments? Could you help? Jun 27, 2023 at 11:01
• @SonerfromTheOttomanEmpire Quite frankly, I'm not really good at O calculation so, if you don't mind I let this question to be answered by someone else. Jun 27, 2023 at 12:09
• Thank you again. Jun 27, 2023 at 12:27
• I agree that method names should start with a verb, but Partition is both a noun and a verb. In such cases where there is an ambiguity one should take extra step to clarify, so GetPartition would be the better choice. Jun 27, 2023 at 14:43

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.