generation/bugs-QuixBugs/bugs/KTH.java/src/java_programs/KTH.java
package java_programs;
import java.util.*;
import java_programs.Node;
/*

 */
public class KTH {
    public static Integer kth(ArrayList<Integer> arr, int k) {
        int pivot = arr.get(0);
        ArrayList<Integer> below, above;
        below = new ArrayList<Integer>(arr.size());
        above = new ArrayList<Integer>(arr.size());
        for (Integer x : arr) {
            if (x < pivot) {
                below.add(x);
            } else if (x > pivot) {
                above.add(x);
            }
        }

        int num_less = below.size();
        int num_lessoreq = arr.size() - above.size();
        if (k < num_less) {
            return kth(below, k);
        } else if (k >= num_lessoreq) {
            return kth(above, k);
        } else {
            return pivot;
        }
    }
}
