Binary Insertion Sort ใน Java: ใช้ Binary Search หาตำแหน่ง Insert

Binary Insertion Sort

Binary Insertion Sort ปรับปรุง Insertion Sort โดยใช้ Binary Search หาตำแหน่งที่จะ insert แทน Linear Search ลดการเปรียบเทียบจาก O(n) เป็น O(log n) ต่อ element

⚠️ หมายเหตุ: โค้ดต้นฉบับเป็น Cocktail Sort ไม่ใช่ Binary Insertion Sort

โค้ดที่ให้มา implement Cocktail Sort (Bidirectional Bubble Sort) ไม่ใช่ Binary Insertion Sort ข้างล่างคือ Binary Insertion Sort ที่ถูกต้อง

Binary Insertion Sort ที่ถูกต้อง

import java.util.Arrays; 

public class Demo { 
    // Binary Search หาตำแหน่ง insert ใน sorted subarray arr[0..end]
    static int binarySearchInsertPos(int[] arr, int key, int start, int end) { 
        while (start <= end) { 
            int mid = start + (end - start) / 2; 
            if (arr[mid] == key) return mid; // หรือ mid+1 สำหรับ stable
            if (arr[mid] < key) start = mid + 1; 
            else end = mid - 1; 
        } 
        return start; // insertion point
    } 
    
    static void binaryInsertionSort(int[] arr) { 
        for (int i = 1; i < arr.length; i++) { 
            int key = arr[i]; 
            
            // หาตำแหน่ง insert ใน arr[0..i-1]
            int pos = binarySearchInsertPos(arr, key, 0, i - 1); 
            
            // Shift elements to make space
            for (int j = i - 1; j >= pos; j--) 
                arr[j + 1] = arr[j]; 
            
            arr[pos] = key; 
        } 
    } 
    
    public static void main(String[] args) { 
        int[] arr = {6, 8, 34, 21, 0, 1, 98, 64, 6}; 
        
        System.out.println("ก่อน: " + Arrays.toString(arr)); 
        binaryInsertionSort(arr); 
        System.out.println("หลัง:  " + Arrays.toString(arr)); 
    } 
}

ผลลัพธ์

ก่อน: [6, 8, 34, 21, 0, 1, 98, 64, 6]
หลัง:  [0, 1, 6, 6, 8, 21, 34, 64, 98]

คำอธิบาย Binary Insertion Sort

1. Outer loop: i = 1 ถึง n-1 (เหมือน Insertion Sort)
2. Key = arr[i]
3. Binary Search ใน arr[0..i-1] (ซึ่งเรียงแล้ว) หา insertion position
4. Shift elements [pos..i-1] ไปขวา 1 ช่อง
5. Insert key ที่ pos

ความซับซ้อน

→ ยังคงเป็น O(n²) เพราะ Shifting ยังเป็น O(n) แต่ลด Comparisons ลง

Cocktail Sort (จากโค้ดต้นฉบับ)

// Cocktail Sort = Bidirectional Bubble Sort
void cocktailSort(int[] arr) { 
    boolean swapped = true; 
    int start = 0, end = arr.length; 
    
    while (swapped) { 
        swapped = false; 
        
        // Left to right (like bubble sort)
        for (int i = start; i < end - 1; i++) 
            if (arr[i] > arr[i+1]) { swap(arr,i,i+1); swapped = true; } 
        
        if (!swapped) break; 
        swapped = false; 
        end--; 
        
        // Right to left
        for (int i = end - 1; i >= start; i--) 
            if (arr[i] > arr[i+1]) { swap(arr,i,i+1); swapped = true; } 
        
        start++; 
    } 
}

เปรียบเทียบ