Its related to quick sort Pens and caps You have a mixed pil

It\'s related to quick sort.

Pens and caps. You have a mixed pile of pens and caps and need to quickly find the corresponding pairs of pens and caps. Each pen matches exactly one cap, and each cap matches exactly one pen. By fitting a pen and cap together, you can see which is bigger. But it is not possible to directly compare two pens or two caps. Given an efficient method for solving the problem. Hint: customize quicksort to the problem. c p [ [ 0 0 ] ] , , c p [ [ 1 1 ] ] , , . . . . . . , , c p [ [ n n 1 1 ] ] Description of the solution. There are n pens and n caps in no particular order. A simple modification of Quicksort shows that there are randomized algorithms O c (n [ lo i g ] n) whose expected number of comparisons (and running time) is : pick a random cap , p[ j] compare it to all the pens, and find its matching pen . This step divides the pens into two batches: c c p [ [ [ i i j ] ] ] one batch too big for (and are all bigger than ) , and another batch too small for (and all p p [ [ j j ] ] smaller than ). Next, match with all the caps, and similarly divide them into two batches, one c p p [ [ [ i j j ] ] ] batch too big for and thus bigger than , and another batch too small for , and are thus c[i] smaller than . This splits the problem into two problems, one consisting of the pens and caps smaller than the matched pair and one consisting of the larger ones. Repeating in this manner yields an algorithm whose expected running time can be analyzed by imitating the known analysis for Quicksort. Your task is to provide the necessary Java implementation to obtain the described solution.

Solution

public class CapAndPensMatch

{

    public static void main(String[] args)

    {

        matchPairs(cap, pens, 0, len);

    }

    private static void matchPairs(char[] cap, char[] pens, int low, int high)

    {

        if (low < high)

        {

            int pivot = partition(cap, low, high, pens[high]);

            partition(bolts, low, high, cap[pivot]);

            matchPairs(cap, pens, low, pivot-1);

            matchPairs(cap, pens, pivot+1, high);

        }

    }

    private static int partition(char[] arr, int low, int high, char pivot)

    {

        int i = low;

        char temp1, temp2;

        for (int j = low; j < high; j++)

        {

            if (arr[j] < pivot){

                temp1 = arr[i];

                arr[i] = arr[j];

                arr[j] = temp1;

                i++;

            } else if(arr[j] == pivot){

                temp1 = arr[j];

                arr[j] = arr[high];

                arr[high] = temp1;

                j--;

            }

        }

        temp2 = arr[i];

        arr[i] = arr[high];

        arr[high] = temp2;

        return i;

    }

}