Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सरणी रोटेशन के लिए ब्लॉक स्वैप एल्गोरिदम


सरणी रोटेशन के लिए ब्लॉक स्वैप एल्गोरिदम एक कुशल एल्गोरिदम है जिसका उपयोग सरणी रोटेशन के लिए किया जाता है। यह आपका काम O(n) समय जटिलता में कर सकता है।

तो, सरणी रोटेशन में, हमें आकार n की एक सरणी arr[] और एक संख्या k दी जाती है जो रोटेट किए जाने वाले तत्वों की संख्या को परिभाषित करती है।

सरणी रोटेशन पर उदाहरण -

इनपुट -

arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (रोटेशन की संख्या.)

आउटपुट -

{1, 8, 9, 2, 4, 6}

व्याख्या - रोटेशन पर, हम एक तत्व को अंतिम स्थिति में शिफ्ट करेंगे और अगले तत्वों को एक स्थिति शिफ्ट करेंगे।

इंडेक्स 0 पर तत्व इंडेक्स n-1 पर शिफ्ट होगा। और बाकी तत्व पिछले इंडेक्स पर शिफ्ट होंगे।

ब्लॉक स्वैप एल्गोरिदम

ब्लॉक स्वैप एल्गोरिदम का उपयोग सरणी रोटेशन को पूरी तरह से करने के लिए किया जाता है।

एल्गोरिदम

चरण 1 - सरणी को k को विभाजन बिंदु मानकर दो उप-सरणियों में विभाजित करें। मान लें वे X = arr[0...k-1] और Y = arr[k...n-1] हैं।

चरण 2 - नीचे दिए गए चरणों का पालन करें जब तक X और Y का आकार समान न हो जाए।

चरण 2.1 - यदि X का आकार > Y है, तो X को दो भागों X1 और X2 में विभाजित करें ताकि X1 का आकार Y के आकार के बराबर हो। फिर उप-सरणी X1 और Y को स्वैप करें। यह मूल सरणी निर्माण को X1X2Y से YX2X1 में बदल देगा।

चरण 2.2 - यदि Y का आकार > X है, तो Y को दो भागों Y1 और Y2 में विभाजित करें ताकि Y2 का आकार X के आकार के बराबर हो। फिर उप-सरणी X और Y2 को स्वैप करें। यह मूल सरणी निर्माण को XY1Y2 से Y2Y1X में बदल देगा।

चरण 3 - जब X और Y का आकार समान हो जाए, तो उन्हें स्वैप करें।

इस एल्गोरिदम को कोड के उसी हिस्से को बार-बार कॉल करने की आवश्यकता होती है। इस दोहराव कॉल को दो दृष्टिकोणों का उपयोग करके प्राप्त किया जा सकता है। वे पुनरावर्ती दृष्टिकोण (recursive approach) और पुनरावृत्त दृष्टिकोण (iterative approach) हैं। हम प्रोग्राम का उपयोग करके दृष्टिकोण पर चर्चा करेंगे।

कार्यक्रम उदाहरण (पुनरावर्ती दृष्टिकोण)

#include <iostream>
using namespace std;

void swapSubArray(int arr[], int start, int end, int k){
    int temp;
    for(int i = 0; i < k; i++){
        temp = arr[start + i];
        arr[start + i] = arr[end + i];
        arr[end + i] = temp;
    }
}

void blockSwapAlgo(int arr[], int k, int n) {
    if(k == 0 || k == n)
        return;
    if(k < (n-k)) {
        swapSubArray(arr, 0, (n-k), k);
        blockSwapAlgo(arr, k, (n-k));
    }
    else if(k > (n-k)){
        swapSubArray(arr, 0, k, (n-k));
        blockSwapAlgo((arr+n-k), (2*k-n), k);
    }
    else{
        swapSubArray(arr, 0, (n-k), k);
        return;
    }
}

int main() {
    int arr[] = {4, 6, 1, 8, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "रोटेशन से पहले सरणी :\t";
    for(int i = 0; i<size; i++)
        cout << arr[i] << " ";
    blockSwapAlgo(arr, k, size);
    cout << "\n" << k << " बार रोटेट करने के बाद सरणी :\t";
    for(int i = 0; i<size; i++)
        cout << arr[i] << " ";
    return 0;
}

आउटपुट

रोटेशन से पहले सरणी : 4 6 1 8 9 2
3 बार रोटेट करने के बाद सरणी : 8 9 2 4 6 1

कार्यक्रम उदाहरण (पुनरावृत्त दृष्टिकोण)

#include <iostream>
using namespace std;

void swapSubArray(int arr[], int start, int end, int k){
    int temp;
    for(int i = 0; i < k; i++){
        temp = arr[start + i];
        arr[start + i] = arr[end + i];
        arr[end + i] = temp;
    }
}

void blockSwapAlgoIt(int arr[], int k, int size) {
    int i, j;
    if(k == 0 || k == size)
        return;
    i = k;
    j = size - k;
    while (i != j) {
        if(i < j){
            swapSubArray(arr, k-i, k+j-i, i);
            j -= i;
        }
        else{
            swapSubArray(arr, k-i, k, j);
            i -= j;
        }
    }
    swapSubArray(arr, k-i, k, i);
}

int main() {
    int arr[] = {4, 6, 1, 8, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "रोटेशन से पहले सरणी :\t";
    for(int i = 0; i<size; i++)
        cout << arr[i] << " ";
    blockSwapAlgoIt(arr, k, size);
    cout << "\n" << k << " बार रोटेट करने के बाद सरणी :\t";
    for(int i = 0; i<size; i++)
        cout << arr[i] << " ";
    return 0;
}

आउटपुट

रोटेशन से पहले सरणी : 4 6 1 8 9 2
3 बार रोटेट करने के बाद सरणी : 8 9 2 4 6 1
  1. C++ में सरणी के एलिमेंट्स का गुणनफल C++ में सरणी के एलिमेंट्स का गुणनफल

    पूर्णांक एलिमेंट्स की एक सरणी दी गई है और कार्य सरणी के एलिमेंट्स को गुणा करना और प्रदर्शित करना है। उदाहरण इनपुट-: arr[]={1,2,3,4,5,6,7} आउटपुट-: 1 x 2 x 3 x 4 x 5 x 6 x 7 = 5040 इनपुट-: arr[]={3, 4,6, 2, 7, 8, 4} आउटपुट-: 3 x 4 x 6 x 2 x 7 x 8 x 4 = 32256 नीचे दिए गए प्रोग्राम में उपयोग किया गया द

  1. - ऐरे रोटेशन के लिए रिवर्सल एल्गोरिदम का जावा प्रोग्राम

    ऐरे रोटेशन के लिए रिवर्सल एल्गोरिदम को लागू करने के लिए जावा प्रोग्राम निम्नलिखित है: उदाहरण import java.io.*; public class Demo{ static void rotate_left(int my_arr[], int no_of_rotation){ int n = my_arr.length; array_reversal(my_arr, 0, no_of_rotation - 1); array_r

  1. - ऐरे रोटेशन के लिए जावा प्रोग्राम

    ऐरे रोटेशन के लिए जावा प्रोग्राम निम्नलिखित है: उदाहरण public class Demo{ void rotate_left(int my_arr[], int d, int len){ d = d % len; int i, j, k, temp; int divisor = greatest_Common_divisor(d, len); for (i = 0; i < divisor; i++){ temp = my_