Reversal Algorithm สำหรับ Array Rotation ใน Java

Reversal Algorithm คืออะไร?

อัลกอริทึมหมุนอาร์เรย์ (Array Rotation) ด้วยการ กลับลำดับ (Reverse) 3 ครั้ง ทำได้ใน O(n) time และ O(1) space

หลักการ (Left Rotation by d)

1. Reverse ส่วนแรก: arr[0..d-1]
2. Reverse ส่วนที่สอง: arr[d..n-1]
3. Reverse ทั้งอาร์เรย์: arr[0..n-1]

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

import java.io.*; 

public class Demo { 
    // หมุนซ้าย d ตำแหน่ง
    static void rotateLeft(int[] arr, int d) { 
        int n = arr.length; 
        d = d % n; // จัดการ d > n
        
        reverse(arr, 0, d - 1);       // ขั้นตอน 1
        reverse(arr, d, n - 1);       // ขั้นตอน 2
        reverse(arr, 0, n - 1);       // ขั้นตอน 3
    } 
    
    // กลับลำดับในช่วง [start, end]
    static void reverse(int[] arr, int start, int end) { 
        while (start < end) { 
            int temp = arr[start]; 
            arr[start] = arr[end]; 
            arr[end] = temp; 
            start++; 
            end--; 
        } 
    } 
    
    public static void main(String[] args) { 
        int[] arr = {45, 67, 89, 91, 23, 0, 11}; 
        
        System.out.println("ก่อนหมุน: " + Arrays.toString(arr)); 
        rotateLeft(arr, 4); 
        System.out.println("หลังหมุนซ้าย 4: " + Arrays.toString(arr)); 
    } 
}

ผลลัพธ์

ก่อนหมุน: [45, 67, 89, 91, 23, 0, 11] 
หลังหมุนซ้าย 4: [23, 0, 11, 45, 67, 89, 91]

การตรวจสอบ (Trace)

Original:  [45, 67, 89, 91, 23, 0, 11]  d=4, n=7

1. Reverse [0..3]:     [91, 89, 67, 45, 23, 0, 11]
2. Reverse [4..6]:     [91, 89, 67, 45, 11, 0, 23]
3. Reverse [0..6]:     [23, 0, 11, 45, 67, 89, 91]  ✓

Right Rotation

หมุนขวา d ตำแหน่ง = หมุนซ้าย (n-d) ตำแหน่ง

static void rotateRight(int[] arr, int d) { 
    rotateLeft(arr, arr.length - (d % arr.length)); 
}

เปรียบเทียบวิธีหมุนอาร์เรย์

Java Built-in (สำหรับ List)

List list = new ArrayList<>(Arrays.asList(1,2,3,4,5)); 
Collections.rotate(list, 2); // หมุนขวา 2
Collections.rotate(list, -2); // หมุนซ้าย 2