Hello.

There are three tasks that imply one big:

  1. Implement a quick sort algorithm (made) .
  2. Implement a randomized quick sort algorithm (made) .
  3. Using the quick sort method to solve the following problem.
    " Nuts and bolts ":
    The unorganized carpenter has a mixed set of N nuts and N bolts. The goal is to find the matching pair of nuts and bolts. Each nut corresponds exactly to one bolt, and each bolt corresponds exactly to one nut. By connecting the nut and the bolt to each other, the carpenter can learn more from them (however, he cannot directly compare two nuts or two bolts).
    Develop an algorithm for this task that uses an average of N log (N) comparisons.

I did the first two, but with an understanding of the third task I have problems:

  1. Initially, a single array should be passed to the method, or two?
  2. Should the method sort or look for the same values ​​in two arrays (nut-bolt pairs)?

I would also be very grateful if I could chew on this task, as far as possible.

Thank.

  • one
    @qwesc: What does it mean to “learn more from them”? - VladD
  • How are your nuts and bolts represented? If they are in the same array and you pass it, then> however, it cannot directly compare two nuts or two bolts you will compare 2 nuts and 2 bolts. In the case of two arrays, you can both sort and match the elements. - iksuy
  • All I have is the task text. No explanation, examples or input-output .. - qwesc
  • Is it clear to you what N log (N) means? - smackmychi
  • The running time of the algorithm. n is the length of the array. - qwesc

1 answer 1

To solve the problem in two ways:

  1. Iterative solution
  2. Recursive solution

Here are two ways to describe your question in detail, see here .