find the kth smallest element in an array in csharp

Here's an implementation of finding the kth smallest element in an array using C# and quickselect algorithm:

main.cs
public static int FindKthSmallest(int[] array, int k)
{
    if (k < 1 || k > array.Length)
        throw new ArgumentException("Invalid k value");

    int left = 0;
    int right = array.Length - 1;
    while (left <= right)
    {
        int pivotIndex = Partition(array, left, right);

        if (pivotIndex == k - 1)
            return array[pivotIndex];
        else if (pivotIndex > k - 1)
            right = pivotIndex - 1;
        else
            left = pivotIndex + 1;
    }

    throw new Exception("Kth smallest element not found");
}

private static int Partition(int[] array, int left, int right)
{
    int pivotValue = array[right];
    int pivotIndex = left;

    for (int i = left; i < right; i++)
    {
        if (array[i] < pivotValue)
        {
            Swap(array, i, pivotIndex);
            pivotIndex++;
        }
    }

    Swap(array, pivotIndex, right);
    return pivotIndex;
}

private static void Swap(int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
1040 chars
47 lines

The FindKthSmallest method takes two parameters: the target array and the value of k. The method first checks whether the value of k is valid or not. If k is less than 1 or greater than the length of the array, an ArgumentException is thrown.

The method then initializes two pointers left and right, representing the left and right boundaries of the array. A loop is used to perform the quickselect algorithm to find the kth smallest element in the array. Inside the loop, the Partition method is called to partition the array into two parts: a left sub-array containing elements smaller than a pivot value, and a right sub-array containing elements greater than or equal to the pivot value. If the pivot index equals k-1, the method returns the pivot value. Otherwise, the loop updates the left and right boundaries accordingly and continues until the kth smallest element is found.

The Partition method takes three parameters: the input array, the left boundary index, and the right boundary index. It selects the last element of the array as the pivot value and performs a partition operation to move all elements smaller than the pivot value to the left sub-array and all elements greater than or equal to the pivot value to the right sub-array. It returns the pivot index after the partition operation.

Lastly, the Swap method is used to swap two elements in the input array.

Overall, the time complexity of the algorithm is O(n), where n is the length of the array. The worst-case time complexity is O(n^2) if the array is sorted in descending order.