### Nuts and bolts problem sorting quicksort matching randomizedquicksort    Posted: 7 years ago Updated: 6 years ago Edit answers (1) views (8764)

You are given a mixed pile of n nuts and n bolts. Each nut exactly fits one bolt and vice-versa. You can see which one is bigger, smaller or equal by fitting a nut and bolt together, but you can't compare two nuts or two bolts directly. How will you design an algorithm to find the matching pairs of nuts and bolts.

 Posted: 7 years ago 0 0 Edit We can find the matching pairs of nuts and bolts by modifying randomized quicksort. Pick a random bolt $$b$$ . Compare bolt $$b$$ with all the nuts, partition the nuts into those of size lessThan $$b$$ and greaterThan $$b$$. Partition the bolts - Since we can't compare bolt to bolt and from the last step we know the matching nut $$n$$ to bolt $$b$$, we compare $$n$$ to all the bolts and partition the bolts into those of the size lessThan $$n$$ and greaterThan $$n$$. Recurse for the lessThan and greaterThan partitions of nuts and bolts. Running time of this algorithm is $$O(n^{2})$$.Let the nuts be denoted by $$[a_1, a_2,...,a_n]$$ and bolts be $$[b_1, b_2,...,b_n]$$.for i = 1 to n do for j = 1 to n do if a(i) matches b(j) pair (a(i), b(j)); return all the pairs