नट और बोल्ट समस्या

विभिन्न नटों की सूची और बोल्ट की दूसरी सूची दी गई है। हमारा काम दी गई सूची से नट और बोल्ट का सही मिलान करना है, और उस नट को बोल्ट के साथ मिलाना है, जब वह मेल खाता है।

इस समस्या का समाधान त्वरित छँटाई तकनीक द्वारा किया जाता है। बोल्ट के अंतिम तत्व को धुरी के रूप में लेते हुए, नट सूची को पुनर्व्यवस्थित करें और उस नट की अंतिम स्थिति प्राप्त करें जिसका बोल्ट धुरी तत्व है। नट सूची को विभाजित करने के बाद, हम चयनित नट का उपयोग करके बोल्ट सूची को विभाजित कर सकते हैं। सभी मैचों को प्राप्त करने के लिए बाएं और दाएं उप-सूचियों के लिए समान कार्य किए जाते हैं।

इनपुट और आउटपुट

Input:
The lists of locks and keys.
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
Output:
After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

एल्गोरिदम

विभाजन (सरणी, निम्न, उच्च, धुरी)

इनपुट: एक सरणी, निम्न और उच्च अनुक्रमणिका, धुरी तत्व।

आउटपुट: धुरी तत्व का अंतिम स्थान।

Begin
   i := low
   for j in range low to high, do
      if array[j] < pivot, then
         swap array[i] and array[j]
         increase i by 1
      else if array[j] = pivot, then
         swap array[j] and array[high]
         decrease j by 1
   done

   swap array[i] and array[high]
   return i
End

nutAndBoltMatch(नट, बोल्ट, लो, हाई)

इनपुट: नट की सूची, बोल्ट की सूची, सरणी का निचला और उच्च सूचकांक।

आउटपुट: प्रदर्शित करें कि कौन सा नट किस बोल्ट के लिए है।

Begin
   pivotLoc := partition(nuts, low, high, bolts[high])
   partition(bolts, low, high, nuts[pivotLoc])
   nutAndBoltMatch(nuts, bolts, low, pivotLoc-1)
   nutAndBoltMatch(nuts, bolts, pivotLoc + 1, high)
End

उदाहरण

#include<iostream>
using namespace std;

void show(char array[], int n) {
   for(int i = 0; i<n; i++)
      cout << array[i] << " ";
}

int partition(char array[], int low, int high, char pivot) {    //find location of pivot for quick sort
   int i = low;
   for(int j = low; j<high; j++) {
      if(array[j] <pivot) {    //when jth element less than pivot, swap ith and jth element
         swap(array[i], array[j]);
         i++;
      }else if(array[j] == pivot) {    //when jth element is same as pivot, swap jth and last element
         swap(array[j], array[high]);
         j--;
      }
   }
   swap(array[i], array[high]);
   return i;    //the location of pivot element
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
   if(low < high) {
      int pivotLoc = partition(nuts, low, high, bolts[high]);   //choose item from bolt to nut partitioning
      partition(bolts, low, high, nuts[pivotLoc]);    //place previous pivot location in bolt also
      nutAndBoltMatch(nuts, bolts, low, pivotLoc - 1);
      nutAndBoltMatch(nuts, bolts, pivotLoc+1, high);
   }
}

int main() {
   char nuts[] = {')','@','*','^','(','%','!','$','&','#'};
   char bolts[] = {'!','(','#','%',')','^','&','*','$','@'};
   int n = 10;
   nutAndBoltMatch(nuts, bolts, 0, n-1);
   cout << "After matching nuts and bolts:"<< endl;
   cout << "Nuts:  "; show(nuts, n); cout << endl;
   cout << "Bolts: "; show(bolts, n); cout << endl;
}

आउटपुट

After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^