Prune and search is a method for finding an optimal value by iteratively dividing a search space into two parts – the promising one, which contains the optimal value and is recursively searched and the second part without optimal value, which is pruned (thrown away). This paradigm is very similar to well know divide and conquer algorithms.

Finding n-th largest number

A naive approach to find the n-th largest number in the given array would sort the whole array (using some algorithm) and then it would return the n-th value. But this solution is very ineffective.

A better solution is to employ a modified prune-and-search version of quicksort algorithm. The original quicksort algorithm in the first phase divides the array into three parts – the first contains only elements higher than the pivot, the second part is the pivot itself, and the third part contains elements with less or equal value in comparison to the pivot. In the second phase quicksort recursively calls itself to sort part one and part three (pivot is already placed at its final position).

Modified prune-and-search algorithm advances similarly, in the first phase the array is divided exactly as in original algorithm, but in phase 2 only the part, which contains the n-th index, gets sorted. The two parts remaining are pruned, because they cannot contain a solution.

Complexity

While the original approach has a expected complexity, modified algorithm finds the n-th largest number in a expected complexity, where is a small constant (approximately 4).

Code

   /**
     * Prune and search
     * @param array array to be searched in
     * @param index order of the searched value (indexed starting at 0)
     * @param left first elemenent, which can be touched
     * @param right first element, which cant be touched
     * @return n-th largest value
     */
    public static int pruneAndSearch(int[] array, int index, int left, int right) {
        int boundary = left;
        for (int i = left + 1; i < right; i++) { 
            if (array[i] > array[left]) { //place after the pivot every value, which is larger than the pivot
                swap(array, i, ++boundary);
            }
        }
        swap(array, left, boundary); //place pivot in the middle
        //quicksort end

        if (boundary == index) return array[boundary]; //found
        else if (boundary > index) return pruneAndSearch(array, index, left, boundary); //prune the right branch
        else return pruneAndSearch(array, index, boundary + 1, right); //prune the left branch  
    }

    /**
     * Swap elements in the given array
     * @param array array
     * @param left index of the element 1
     * @param right index of the element 2
     */
    private static void swap(int[] array, int left, int right) {
        int tmp = array[right];
        array[right] = array[left];
        array[left] = tmp;
    }

Literature

• Prune-and-search. In . [s.l.] : [s.n.], 2006 [2010-03-15]. Available at WWW: <http://www.cs.duke.edu/courses/fall05/cps230/L-03.pdf>.