//QuickSelectDemo.java

import java.util.Arrays;
import java.util.Scanner;

public class QuickSelectDemo
{
    private static int partition
    (
        int[] numbers,
        int startIndex,
        int endIndex
    )
    {
        // Select the middle value as the pivot.
        int midpoint = startIndex + (endIndex - startIndex) / 2;
        int pivot = numbers[midpoint];

        // "low" and "high" start at the ends of the array segment
        // and move towards each other.
        int low = startIndex;
        int high = endIndex;

        boolean done = false;
        while (!done)
        {
            // Increment low while numbers[low] < pivot
            while (numbers[low] < pivot)
            {
                low = low + 1;
            }

            // Decrement high while pivot < numbers[high]
            while (pivot < numbers[high])
            {
                high = high - 1;
            }

            // If low and high have crossed each other, the loop
            // is done. If not, the elements are swapped, low is
            // incremented and high is decremented.
            if (low >= high)
            {
                done = true;
            }
            else
            {
                int temp = numbers[low];
                numbers[low] = numbers[high];
                numbers[high] = temp;
                low = low + 1;
                high = high - 1;
            }
        }

        // "high" is the last index in the left segment.
        return high;
    }

    private static int QuickSelect
    (
        int[] numbers,
        int startIndex,
        int endIndex,
        int k
    )
    {
        if (startIndex >= endIndex)
        {
            return numbers[startIndex];
        }

        int lowLastIndex = partition(numbers, startIndex, endIndex);
        if (k <= lowLastIndex)
        {
            return QuickSelect(numbers, startIndex, lowLastIndex, k);
        }
        return QuickSelect(numbers, lowLastIndex + 1, endIndex, k);
    }

    public static void main(String[] args)
    {
        int[] numbers = { 6, 2, 12, 8, 4, 3, 19, 17, 22, 41, 7, 1, 15 };
        System.out.println("Original array: " + Arrays.toString(numbers));

        // Get k from user
        Scanner scnr = new Scanner(System.in);
        int k = scnr.nextInt();
        int kthValue = QuickSelect(numbers, 0, numbers.length - 1, k);

        // Display results, and compare to sorted list.
        System.out.printf
        (
            "After QuickSelect(%d): %s%n",
            k,
            Arrays.toString(numbers)
        );
        System.out.printf
        (
            "QuickSelect(%d) result: %d%n",
            k,
            kthValue
        );

        System.out.println();
        Arrays.sort(numbers);
        System.out.println("Sorted list: " + Arrays.toString(numbers));
        System.out.printf("kth sorted item: %d%n", numbers[k]);
    }
}