Array Rotation ใน Java: Juggling Algorithm (GCD)

Juggling Algorithm สำหรับ Array Rotation

อัลกอริทึมหมุนอาร์เรย์ที่ใช้ GCD (Greatest Common Divisor) แบ่งอาร์เรย์เป็น gcd(n, d) เซต แล้วหมุนในแต่ละเซตแยกกัน ทำได้ใน O(n) time, O(1) space

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

public class Demo { 
    // หมุนซ้าย d ตำแหน่ง
    void rotateLeft(int[] arr, int d, int n) { 
        d = d % n; // จัดการ d >= n
        int gcd = gcd(d, n); 
        
        for (int i = 0; i < gcd; i++) { 
            int temp = arr[i]; 
            int j = i; 
            
            while (true) { 
                int k = j + d; 
                if (k >= n) k -= n; // wrap around
                if (k == i) break;  // กลับมาตำแหน่งเดิม
                arr[j] = arr[k]; 
                j = k; 
            } 
            arr[j] = temp; 
        } 
    } 
    
    // แสดงอาร์เรย์
    void displayArray(int[] arr, int size) { 
        for (int i = 0; i < size; i++) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 
    
    // GCD แบบ Recursive (Euclidean Algorithm)
    int gcd(int a, int b) { 
        if (b == 0) return a; 
        return gcd(b, a % b); 
    } 
    
    public static void main(String[] args) { 
        Demo demo = new Demo(); 
        int[] arr = {5, 7, 89, 91, 34, 21, 11, 0}; 
        
        System.out.println("ก่อนหมุน: "); 
        demo.displayArray(arr, arr.length); 
        
        demo.rotateLeft(arr, 2, arr.length); 
        
        System.out.println("หลังหมุนซ้าย 2: "); 
        demo.displayArray(arr, arr.length); 
    } 
}

ผลลัพธ์

ก่อนหมุน: 
5 7 89 91 34 21 11 0 
หลังหมุนซ้าย 2: 
89 91 34 21 11 0 5 7

คำอธิบายการทำงาน

เมื่อ n=8, d=2 → gcd(8,2)=2 → มี 2 เซต (cycles):

• เซต 1 (i=0): index 0 → 2 → 4 → 6 → 0 (cycle)
• เซต 2 (i=1): index 1 → 3 → 5 → 7 → 1 (cycle)

แต่ละเซตย้ายค่าแบบวนรอบ (juggle) จนกลับมาตำแหน่งเริ่มต้น

Trace เซต 1 (i=0)

temp = arr[0] = 5
j=0: k=2, arr[0]=arr[2]=89, j=2
j=2: k=4, arr[2]=arr[4]=34, j=4
j=4: k=6, arr[4]=arr[6]=11, j=6
j=6: k=8→0, k==i break
arr[6]=temp=5
Result: [89, 7, 34, 91, 11, 21, 5, 0]

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

Java Built-in (List)

List list = new ArrayList<>(Arrays.asList(arr)); 
Collections.rotate(list, -d); // negative = left rotate