The Dutch national flag problem is to rearrange an array of characters R, W, and

Question

The Dutch national flag problem is to rearrange an array of characters R, W, and B (red, white, and blue are the colors of the Dutch national flag) so that all the R's come first, the W's come next, and the B's come last. [Dij76] Design a linear in-place algorithm for this problem. Explain how a solution to the Dutch national flag problem can be used in quicksort. Implement quicksort in the language of your choice. Run your program on a sample of inputs to verify the theoretical assertions about the algorithm's efficiency. Nuts and bolts You are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger than the bolt, smaller than the bolt, or matches the bolt exactly. However, there is no way to compare two nuts together or two bolts together. The problem is to match each bolt to its nut. Design an algorithm for this problem with average-case efficiency in (n log n). [Raw91]

Explanation / Answer

public class NutsAndBolt
{

public static void main(String[] args)
{
  
char nuts[] = {'@', '#', '$', '%', '^', '&'};
char bolts[] = {'$', '%', '&', '^', '@', '#'};

// Method based on quick sort which matches nuts and bolts
matchPairs(nuts, bolts, 0, 5);

System.out.println("Matching nuts and bolts are : ");
print(nuts);
print(bolts);
}

// Method to print the array
private static void print(char[] a) {
for (char ch : a){
System.out.print(ch + " ");
}
System.out.print(" ");
}

  
private static void matchPairs(char[] nuts, char[] bolts, int low,
int high)
{
if (low < high)
{
  
int pivot = partition(nuts, low, high, bolts[high]);

  
partition(bolts, low, high, nuts[pivot]);


matchPairs(nuts, bolts, low, pivot-1);
matchPairs(nuts, bolts, pivot+1, high);
}
}

  
private static int partition(char[] arr, int low, int high, char pivot)
{
int i = low;
char temp1, temp2;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot){
temp1 = arr[i];
arr[i] = arr[j];
arr[j] = temp1;
i++;
} else if(arr[j] == pivot){
temp1 = arr[j];
arr[j] = arr[high];
arr[high] = temp1;
j--;
}
}
temp2 = arr[i];
arr[i] = arr[high];
arr[high] = temp2;

// Return the partition index of an array based on the pivot
// element of other array.
return i;
}
}

==============================================

Output:

Matching nuts and bolts are :
# $ % & @ ^
# $ % & @ ^

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.