อัลกอริทึม Reversal สำหรับการหมุนอาร์เรย์ (Array Rotation) ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ และต้องหมุนอาร์เรย์ d ตำแหน่งโดยใช้ Reversal Algorithm เช่น:

Input : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2 
Output : arr[] = [3, 4, 5, 6, 7, 1, 2]
Explanation : หมุนอาร์เรย์ d = 2 โดยใช้ Reversal Technique

เราคำนวณขั้นตอนการหมุนด้วย Reversal Technique และสรุปได้ว่า:

• ขั้นแรก กลับ d สมาชิกแรกของอาร์เรย์
• ขั้นที่สอง กลับสมาชิกที่เหลือ
• ขั้นที่สาม กลับอาร์เรย์ทั้งหมด

ด้วยการทำ 3 ขั้นตอนนี้ เราจะได้อาร์เรย์ที่หมุนแล้ว

แนวทางแก้ปัญหา

ในปัญหานี้ เราจะสร้างฟังก์ชันสำหรับกลับอาร์เรย์ก่อน แล้วทำตาม 3 ขั้นตอนข้างต้น

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

void reverseArray(int arr[], int start, int end) {
    // อัลกอริทึมการกลับ
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
    return;
}

void Rotate(int arr[], int d, int n) {
    // ฟังก์ชันหมุน
    if (d == 0) // ไม่ต้องหมุน
        return;
    
    d = d % n; // เมื่อ d เท่ากับ n อาร์เรย์จะกลับสู่เดิม
    
    reverseArray(arr, 0, d - 1);     // กลับ d ตัวแรก
    reverseArray(arr, d, n - 1);     // กลับตัวที่เหลือ
    reverseArray(arr, 0, n - 1);     // กลับทั้งอาร์เรย์
    
    return;
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // อาร์เรย์ที่กำหนด
    int n = sizeof(arr) / sizeof(arr[0]); // ขนาดอาร์เรย์
    int d = 2;
    
    Rotate(arr, d, n);
    
    for (int i = 0; i < n; i++) // พิมพ์อาร์เรย์
        cout << arr[i] << " ";
    cout << "\n";
    
    return 0;
}

ผลลัพธ์

3 4 5 6 7 1 2

คำอธิบายโค้ด

ในวิธีนี้ เราสร้างฟังก์ชันกลับอาร์เรย์รับ 3 พารามิเตอร์: อาร์เรย์, ดัชนีเริ่มต้น, ดัชนีสิ้นสุด แล้วกลับอาร์เรย์ในช่วงนั้น ต่อมาเราใช้ 3 ขั้นตอนตามอัลกอริทึม: กลับ d ตัวแรก, กลับตัวที่เหลือ, กลับทั้งอาร์เรย์ ในฟังก์ชัน Rotate เราทำ d = d % n เพราะถ้าหมุน n ตัวแรก จะได้อาร์เรย์เดิม

สรุป

ในบทความนี้ เราแก้ปัญหาการใช้ Reversal Algorithm สำหรับ Array Rotation เรียนรู้โปรแกรม C++ และแนวทางการแก้ปัญหา สามารถเขียนในภาษาอื่นได้เช่น C, Java, Python หวังว่าจะเป็นประโยชน์