public class Main
{
    public static void main(String[] args)
    {
    String[] A = {"","a","aa","aaa"};
        System.out.println(test_quickselect(A,2));
    }
    // Notkun: String s = test_quickselect(a,k);
    // Fyrir:  a er strengjafylki í einhverri röð , k er heiltala,
    //         0 <= k < a.length.
    // Eftir:  Búið er að umraða a á einhvern hátt og s inniheldur
    //         strenginn sem væri í sæti k ef a væri raðað í
    //         vaxandi röð.
    public static String test_quickselect( String[] a, int k )
    {
        quickselect(a, 0, a.length, k);
        return a[k];
    }

    // Notkun: quickselect( a,i,j,k )
    // Fyrir:  a[i..j-1] er svæði í strengjafylkinu a.
    // Eftir:  Búið er að raða a[i..j-1] í vaxandi röð.
    public static void quickselect( String[] a, int i, int j,int k )
    {
        if( j - i == 1 ) return;
        // Víxlum fyrst á miðstakinu
        // og fremsta stakinu.
        int m = i + (j-i)/2;
        String p = a[m];
        a[m] = a[i];
        a[i] = p;

        int r = i+1;

        for( int s = r; s != j; s++)
        {
            // |p| <p | >=p | ?? |
            //  i   r    s     j
            if( a[s].compareTo(p) < 0 )
            {
                String temp = a[s];
                a[s] = a[r];
                a[r] = temp;
                r++;
            }
        }
        // |p| < p | >=p |
        //  i    r    j
        r--;
        // |p| < p | >=p |
        //  i    r    j
        a[i] = a[r];
        a[r] = p;
        // | <p |p| >=p |
        //   i   r   j
        if( k < r && i != r )
        {
            quickselect(a, i, r, k);
        }
        if( k > r && r + 1 != j )
        {
            quickselect(a, r+1, j, k);
        }
    }
}