Nuts Bolts Problem

code

/**
 * class Comparator {
 *     public:
 *      int cmp(string a, string 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:
    /**
     * @param nuts: a vector of integers
     * @param bolts: a vector of integers
     * @param compare: a instance of Comparator
     * @return: nothing
     */
    void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
        // write your code here
        if(nuts.size() == 0 || bolts.size() == 0)
        {
            return ;
        }

        qsort(nuts, bolts, compare, 0, nuts.size()-1);
    }

    void qsort(vector<string>& nuts, vector<string>& bolts, Comparator compare, int s, int e)
    {
        if(s >= e)
        {
            return ;
        }

        int pos = partition(nuts, bolts[s], compare, s, e);
        partition(bolts, nuts[pos], compare, s, e);

        qsort(nuts, bolts, compare, s, pos-1);
        qsort(nuts, bolts, compare, pos+1, e);
    }

    int partition(vector<string>& str, const string& pivot, Comparator compare, int s, int e)
    {
        for(int i = s; i <= e; i++)
        {
            if(compare.cmp(str[i], pivot) == 0 || compare.cmp(pivot, str[i]) == 0)
            {
                string tmp = str[s];
                str[s] = str[i];
                str[i] = tmp;
                break;
            }
        }

        int l = s;
        int r = e;
        string now = str[l];

        while(l < r)
        {
            while(l < r && (compare.cmp(str[r], pivot) == 1 || compare.cmp(pivot, str[r]) == -1))
            {
                r--;
            }
            str[l] = str[r];

            while(l < r && (compare.cmp(str[l], pivot) == -1 || compare.cmp(pivot, str[l]) == 1))
            {
                l++;
            }
            str[r] = str[l];
        }

        str[l] = now;
        return l;
    }
};