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.
/** * 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); } };