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

परिचय

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

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

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

इनपुट: लॉक्स और कीज़ की सूचियाँ।
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
आउटपुट: नट्स और बोल्ट्स के मिलान के बाद:
Nuts: ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

एल्गोरिदम

partition(array, low, high, pivot)

इनपुट: एक सरणी, निम्न और उच्च इंडेक्स, पिवट तत्व।

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

Begin
    i := low
    j के लिए रेंज low से high तक, करें
        यदि array[j] < pivot, तो
            array[i] और array[j] को स्वैप करें
            i को 1 से बढ़ाएं
        अन्यथा यदि array[j] = pivot, तो
            array[j] और array[high] को स्वैप करें
            j को 1 से घटाएं
    done
    array[i] और array[high] को स्वैप करें
    i लौटाएं
End

nutAndBoltMatch(nuts, bolts, low, high)

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

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

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

उदाहरण (C++ कोड)

#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) {
    // क्विक सॉर्ट के लिए पिवट का स्थान खोजें
    int i = low;
    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            // जब jवां तत्व पिवट से कम हो, ith और jth तत्व को स्वैप करें
            swap(array[i], array[j]);
            i++;
        } else if (array[j] == pivot) {
            // जब jवां तत्व पिवट के समान हो, jth और अंतिम तत्व को स्वैप करें
            swap(array[j], array[high]);
            j--;
        }
    }
    swap(array[i], array[high]);
    return i; // पिवट तत्व का स्थान
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
    if (low < high) {
        int 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);
    }
}

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: ! # $ % & ( ) * @ ^