[LintCode] Nuts & Bolts Problem

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

Example

Nuts represented as array of integers nuts[] = {1, 5, 8, 2}. Bolts represented as array of integers bolts[] = {3, 6, 7, 9}. We will give you a compare function to compare nut with bolt. Sort the nuts in increasing order so that nut match with the bolt with the same position.

Reference quick sort:

/**
 * class Compare {
 *     public:
 *     static int cmp(int a, int b);
 * };
 * You can use Compare::cmp(a, b) to compare nuts "a" and bolts "b",
 * if "a" is bigger than "b", it will return 1, else if they are equal,
 * it will return 0, else if "a" is smaller than "b", it will return -1.
 * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
class Solution {
public:
    void sortNutsAndBolts(vector<int> &nuts, 
                          vector<int> &bolts,
                          int s, int e) {
        if(s >= e) return;
        
        int start = s, end = s, match;
        
        while(end <= e){
            if(Compare::cmp(nuts[end], bolts[s])<=0){
                if(Compare::cmp(nuts[end], bolts[s]) == 0)
                    match = start;
                swap(nuts[start], nuts[end]);
                start ++;
            }
            end ++;
        }
        swap(nuts[start-1], nuts[match]);
        int pivot = start - 1;
        
        start = s;
        end = s;
        while(end <= e) {
            if(Compare::cmp(nuts[pivot], bolts[end])>=0) {
                if(Compare::cmp(nuts[pivot], bolts[end]) == 0)
                    match = start;
                swap(bolts[start], bolts[end]);
                start ++;
            }
            end ++;
        }
        swap(bolts[pivot], bolts[match]);   
        
        sortNutsAndBolts(nuts, bolts, s, pivot-1);
        sortNutsAndBolts(nuts, bolts, pivot+1, e);
    }
    
    void sortNutsAndBolts(vector<int> &nuts, vector<int> &bolts) {
        sortNutsAndBolts(nuts, bolts, 0, bolts.size()-1);
    }
};