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

อัลกอริทึม Block Swap สำหรับการหมุนอาร์เรย์ (array rotation) เป็นอัลกอริทึมที่มีประสิทธิภาพ ใช้สำหรับหมุนอาร์เรย์ ทำงานได้ในเวลา O(n)

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

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

อินพุต −

arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (จำนวนครั้งที่หมุน)

เอาต์พุต −

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

คำอธิบาย − ในการหมุน เราจะเลื่อนองค์ประกอบหนึ่งไปไว้ตำแหน่งสุดท้าย และเลื่อนองค์ประกอบอื่นๆ ไปหนึ่งตำแหน่ง องค์ประกอบที่ดัชนี 0 จะไปอยู่ที่ดัชนี n-1 ส่วนที่เหลือเลื่อนไปดัชนีก่อนหน้า

อัลกอริทึม Block Swap

อัลกอริทึม Block Swap ใช้เพื่อทำการหมุนอาร์เรย์ได้อย่างสมบูรณ์

ขั้นตอนของอัลกอริทึม

ขั้นตอน 1 − แบ่งอาร์เรย์ออกเป็น 2 ส่วนย่อยด้วย k เป็นจุดแบ่ง ให้เป็น X = arr[0...k-1] และ Y = arr[k...n-1]

ขั้นตอน 2 − ทำตามขั้นตอนด้านล่างจนกว่าขนาดของ X และ Y จะเท่ากัน

ขั้นตอน 2.1 − ถ้าขนาดของ X > Y แบ่ง X เป็น 2 ส่วน X1 และ X2 ให้ขนาด X1 เท่ากับขนาด Y แล้วสลับ sub-array X1 และ Y จะเปลี่ยนอาร์เรย์จาก X1X2Y เป็น YX2X1

ขั้นตอน 2.2 − ถ้าขนาดของ Y > X แบ่ง Y เป็น 2 ส่วน Y1 และ Y2 ให้ขนาด Y2 เท่ากับขนาด X แล้วสลับ sub-array X และ Y2 จะเปลี่ยนอาร์เรย์จาก XY1Y2 เป็น Y2Y1X

ขั้นตอน 3 − เมื่อขนาดของ X และ Y เท่ากัน ให้สลับพวกมัน

อัลกอริทึมนี้ต้องการการเรียกซ้ำ (recursive call) ของโค้ดชุดเดียวกัน ซึ่งสามารถทำได้ 2 วิธี คือ Recursive Approach และ Iterative Approach เราจะอภิปรายทั้งสองวิธีด้วยโปรแกรม

ตัวอย่างโปรแกรม (Recursive 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 << "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

ตัวอย่างโปรแกรม (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 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