**Question:**Given an array of nuts of different sizes and array bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently with the given constraint that 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.

**Solution:**Tweak quick sort to achieve it.

**Implementation:**

int split(int *arr, int low, int high, int pivot)

{

int j = low;

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

{

if(arr[i] < pivot)

{

std::swap(arr[i], arr[j]);

++j;

}

else if(arr[i] == pivot)

{

std::swap(arr[i], arr[high]);

--i;

}

}

std::swap(arr[j], arr[high]);

return j;

}

void matchNutsBolts(int *nuts, int *bolts, int low, int high)

{

if(!nuts || !bolts)

return;

if(low < high)

{

int pivot = split(nuts, low, high, bolts[high]);

split(bolts, low, high, nuts[pivot]);

matchNutsBolts(nuts, bolts, low, pivot - 1);

matchNutsBolts(nuts, bolts, pivot + 1, high);

}

}

**Complexity:**O(nlogn)

Hey! I have a doubt. What is the significance of :

ReplyDeleteelse if(arr[i] == pivot)

{

std::swap(arr[i], arr[high]);

--i;

}

What purpose does this solve?