using System;

public class Program

{

    private static void Swap(int[] nums, int i, int j){

        var temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

    private static int Partition(int[] nums, int start, int end){

        var origStart = start; //3

        var origEnd = end; //4

        //2 1 3 5 4 6 

        //last element is the pivot

        var chosenPivot = nums[origEnd]; //4

        end--; //we are not touching the pivot in the while loop //3

        while (start <= end){ //3 < 3

            while (start < origEnd && nums[start] < chosenPivot) start++;

            while (end >= origStart && nums[end] > chosenPivot) end--;

            if (start >= end){

                break;

            }

            Swap(nums, start, end);

        }

​

        Swap(nums,origEnd,end+1); //moving the pivot to its right position

        return end+1;

    }

    public static void Shuffle(int[] nums){

        Random rand = new Random();

        for (int i = nums.Length-1; i >= 1; i--){

            var randomPos = rand.Next(0,i);

            Swap(nums,randomPos,i);

        }

        //print

        Console.WriteLine("shuffled: ");

        foreach (var num in nums){

            Console.Write(num + " ");

        }

        Console.WriteLine();

    }

    public static int FindKthLargest(int[] nums, int k) {

        Shuffle(nums);

        k = nums.Length - k + 1; // k = 6 - 2 + 1 = 5 - 5th from beginning

        var wantedIndex = k - 1; //4

        int start = 0;

        int end = nums.Length - 1;

        while (start < end){ //3 < 4

            var pivotPosition = Partition(nums,start,end);

            if (wantedIndex == pivotPosition)

                break;

            else if (wantedIndex < pivotPosition)

                end = pivotPosition - 1; 

            else

                start = pivotPosition + 1; 

        }

        return nums[wantedIndex];

    }

    public static void Main()

    {

        /*

        Input: [3,2,1,5,6,4] and k = 2

        Output: 5

        */

        var nums = new int[6]{3,2,1,5,6,4};

        var k = 2;

        //Shuffle(nums);

        foreach (var num in nums){

            Console.Write(num + " ");

        }

        Console.WriteLine();

        Console.WriteLine("k: " + k);

        Console.WriteLine(FindKthLargest(nums,k));

    }

}