Hello.

With the help of the quick sorting method working by divide and conquer solve the following problem. "Nuts and bolts": An 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.

Quick sort method:

private void quickSort(int[] array, int start, int end) { if (start >= end) return; int pivot = array[start]; int i = start; int j = end; int temp = 0; while (i <= j) { while (array[i] < pivot) { i++; } while (array[j] > pivot) { j--; } if (i <= j) { temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } } if (start < j) { quickSort(array, start, j); } if (i < end) { quickSort(array, i, end); } }

I ask for help in solving the problem, I will be very grateful.

  • Quick sort here, I think everyone knows. And what exactly did you do? Any ideas on the algorithm? - VladD
  • The point is that the task is not clear enough, so I turned here, maybe someone can help with its solution, I will study it in detail and will keep it in mind in the future. - qwesc
  • one
    hashcode.ru/questions/377974 - that’s your old question. Would update it, or something. - smackmychi
  • Can someone help? - qwesc
  • @qwesc, what's the help? How to find matching pairs in 2 already sorted (sorting you have already written) arrays? Fingering the bolts. Compare the next bolt with nuts, while they are smaller than the bolt and throw them (on the sinker). If approached, then twist and postpone a pair. Otherwise, throw the bolt. Repeat until it's over. - In principle, this is very similar to the merging of 2 arrays (merge). - avp

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.

  • It's pretty funny to see the code (by reference) where they care about overflowing the index (due to the decision about the unsigned type of the index size_t , apparently from the desire to sort, including “giant” arrays), but they do not think at all about optimizing the stack size. Just first you need to deal with shorter segments. We first add a longer segment to the stack, and then a shorter one (and for a recursive implementation, we first send the shorter one to sort). Such optimization will allow to allocate memory for the stack (for the iterative version) once. - avp