Take a Nut, try putting it to all bolts (this is Comparing Nut with Bolt). If Nut goes not go and fit into bolt, keep the bolt on left, if Nut fits loose, keep the bolt on right and keep the bolt and nut which match, at centre. This is pivot of quicksort. All bolts to left of this central Nut+bolt are smaller and all towards right are large than central Nut + bolt. This will take N comparision.
Then take second Nut. try fitting to central bolt. It will not fit. But we will be able to make a decision weather to move left or right. if this Nut is tight on bolt, try smaller bolts on left, else try larger bolts on right. This will take n/2 comparisions and we will find exact bolt fitting this 2nd nut. This process will again divide either left or right bolts into 2 part. and go on. This shold take NlogN time to complete the whole matching process as in case of quick sort. let me know your comments or improvements. Sain On Jun 6, 7:05 pm, sharad <sharad20073...@gmail.com> wrote: > There are N nuts and N bolts, all unique pairs od Nut and Bolt > You cant compare Nut with Nut. > You cant compare Bolt with Bolt > You CAN compare Nut with Bolt > Now how would you figure out matching pairs of nut and bolt from the > given N nut and Bolt. > The basic soln is O(N^2). Give O(NlogN soln) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
