Iterative Quick Sort ใน Java: อัลกอริทึมและการทำงาน

Iterative Quick Sort คืออะไร?

Quick Sort แบบวนซ้ำ (Iterative) ใช้ Stack จำลองการเรียกฟังก์ชัน recursive แทนการใช้ call stack จริง ช่วยหลีกเลี่ยง StackOverflowError สำหรับข้อมูลขนาดใหญ่

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

public class Demo { 
    // สลับค่าสองตำแหน่ง
    void swap(int[] arr, int i, int j) { 
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
    } 
    
    // Partition: เลือก pivot (สุดท้าย) ย้ายค่าน้อยกว่าไปซ้าย มากกว่าไปขวา
    int partition(int[] arr, int low, int high) { 
        int pivot = arr[high]; 
        int i = low - 1; 
        
        for (int j = low; j <= high - 1; j++) { 
            if (arr[j] <= pivot) { 
                i++; 
                swap(arr, i, j); 
            } 
        } 
        swap(arr, i + 1, high); 
        return i + 1; // คืนตำแหน่ง pivot ที่ถูกต้อง
    } 
    
    // Iterative Quick Sort
    void quickSort(int[] arr, int low, int high) { 
        // Stack จำลอง recursive calls
        int[] stack = new int[high - low + 1]; 
        int top = -1; 
        
        // Push initial range
        stack[++top] = low; 
        stack[++top] = high; 
        
        while (top >= 0) { 
            // Pop range
            high = stack[top--]; 
            low = stack[top--]; 
            
            // Partition
            int p = partition(arr, low, high); 
            
            // Push left partition (ถ้ามีสมาชิกมากกว่า 1)
            if (p - 1 > low) { 
                stack[++top] = low; 
                stack[++top] = p - 1; 
            } 
            
            // Push right partition
            if (p + 1 < high) { 
                stack[++top] = p + 1; 
                stack[++top] = high; 
            } 
        } 
    } 
    
    public static void main(String args[]) { 
        Demo ob = new Demo(); 
        int[] arr = {34, 76, 41, 32, 11, 0, 91, 102, -11}; 
        
        ob.quickSort(arr, 0, arr.length - 1); 
        
        System.out.println("หลัง Iterative Quick Sort:"); 
        for (int val : arr) 
            System.out.print(val + " "); 
    } 
}

ผลลัพธ์

หลัง Iterative Quick Sort: 
-11 0 11 32 34 41 76 91 102

คำอธิบายขั้นตอน

1. Swap - ฟังก์ชันช่วยสลับค่า 2 ตำแหน่ง
2. Partition - ใช้ Lomuto partition scheme: เลือก pivot = arr[high], ย้ายค่า ≤ pivot ไปซ้าย คืน index ของ pivot
3. QuickSort (Iterative):
   • สร้าง stack array เก็บคู่ (low, high)
   • Push ช่วงเริ่มต้น (0, n-1)
   • While stack ไม่ว่าง: Pop ช่วง, partition, push ส่วนซ้ายและขวา (ถ้ามีขนาด > 1)

ความซับซ้อน

การปรับปรุง (Optimizations)

• Randomized Pivot - สุ่ม pivot ป้องกัน worst-case บน sorted array
• Median-of-three - เลือก pivot จาก median ของ first, mid, last
• Insertion Sort สำหรับ subarray เล็ก - เร็วกว่าเมื่อ n < 10-20
• Tail Recursion Elimination - เรียก recursive ด้านใหญ่เพียงด้านเดียว ลด stack depth

Java Built-in

Arrays.sort(arr); // Dual-Pivot QuickSort (primitives) 
Arrays.sort(objArr); // TimSort (objects) - stable, O(n log n)