บล็อกอัลกอริธึมการสลับสำหรับการหมุนอาร์เรย์ใน C ++

อัลกอริธึมการสลับบล็อกสำหรับการหมุนอาร์เรย์เป็นอัลกอริธึมที่มีประสิทธิภาพซึ่งใช้สำหรับการหมุนอาร์เรย์ มันสามารถทำงานของคุณในความซับซ้อนของเวลา O(n)

ดังนั้น ในการหมุนอาร์เรย์ เราจะได้รับอาร์เรย์ arr[] ขนาด n และตัวเลข k ที่กำหนดหมายเลข ขององค์ประกอบที่จะหมุน

มาดูตัวอย่างการหมุนอาร์เรย์กัน −

ป้อนข้อมูล −

arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (number of rotations.)

ผลผลิต −

{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 เท่ากัน ให้สลับกัน

อัลกอริทึมนี้ต้องการการเรียกซ้ำไปยังกลุ่มโค้ดเดียวกัน การเรียกซ้ำนี้สามารถทำได้โดยใช้สองวิธี เป็นแนวทางแบบเรียกซ้ำ และ แนวทางการทำซ้ำ . เราจะหารือเกี่ยวกับวิธีการใช้โปรแกรม

ตัวอย่าง

โปรแกรมเพื่อแสดงแนวทางแบบเรียกซ้ำ -

#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, intk){
   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<<"Array before rotations :\t";
   for(int i = 0; i<size; i++)
      cout<<arr[i]<<" ";
   blockSwapAlgo(arr, k, size);
   cout<<"\nArray after rotating "<<k<<" times :\t";
   for(int i = 0; i<size; i++)
      cout<<arr[i]<<" ";
   return 0;
}

ผลลัพธ์

Array before rotations : 4 6 1 8 9 2
Array after rotating 3 times : 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<<"Array before rotations :\t";
   for(int i = 0; i<size; i++)
      cout<<arr[i]<<" ";
   blockSwapAlgoIt(arr, k, size);
   cout<<"\nArray after rotating "<<k<<" times :\t";
   for(int i = 0; i<size; i++)
      cout<<arr[i]<<" ";
   return 0;
}

ผลลัพธ์

Array before rotations : 4 6 1 8 9 2
Array after rotating 3 times : 8 9 2 4 6 1