Question

I have six nuts and six bolts. Exactly one nut goes with each bolt. The nuts are all different sizes, but it’s hard to compare them to each other. (Same for the bolts.) But if I try a nut and a bolt together, it’s easy to see if the nut is smaller than, the same size as, or larger than the bolt. Find a way to use quicksort to match up the nuts and bolts.

Answer 1

Answer:

Explanation:

In order to arrange the corresponding nuts and bolts in order using quicksort algorithm, we need to first create two arrays , one for nuts and another for bolts namely nutsArr[6] and boltsArr[6]. Now, using one of the bolts as pivot, we can rearrange the nuts in the nuts array such that the nuts on left side of the element chosen (i.e, the ith element indexed as nutArr[i]) are smaller than the nut at ith position and nuts to the right side of nutsArr[i] are larger than the nut at position "I". We implement this strategy recursively to sort the nuts array. The reason that we need to use bolts for sorting nuts is that nuts are not comparable among themselves and bolts are not comparable among themselves(as mentioned in the question)

The pseudocode for the given problem goes as follows:

// method to quick sort the elements in the two arrays

quickSort(nutsArr[start...end], boltsArr[start...end]): if start < end: // choose a nut from nutsArr at random randElement = nutsArr[random(start, end+1)] // partition the boltsArr using the randElement random pivot pivot = partition(boltsArr[start...end], randElement) // partition nutsArr around the bolt at the pivot position partition(nutsArr[start...end], boltsArr[pivot]) // call quickSort by passing first partition quickSort(nutsArr[start...pivot-1], boltsArr[start...pivot-1]) // call quickSort by passing second partition quickSort(nutsArr[pivot+1...end], boltsArr[pivot+1...end])

// method to partition the array passed as parameter, it also takes pivot as parameter

partition(character array, integer start, integer end, character pivot)

{

       integer i = start;

loop from j = start to j < end

       {

check if array[j] < pivot

{

swap (array[i],array[j])

               increase i by 1;

           }

 else check if array[j] = pivot

{

               swap (array[end],array[j])

               decrease i by 1;

           }

       }

swap (array[i] , array[end])

       return partition index i;

}