Comb Sort (การจัดเรียงแบบหวี)

Comb Sort เป็นการปรับปรุงจาก Bubble Sort โดยเปรียบเทียบและสลับองค์ประกอบที่ห่างกันด้วย Gap (ช่องว่าง) แทนที่จะเป็นติดกัน ทำให้ "จระเข้" (ค่าน้อยที่อยู่ท้าย) เคลื่อนที่เร็วขึ้น

ความซับซ้อน (Complexity)

Space Complexity: O(1) (In-place)

แนวคิดการทำงาน

1. เริ่ม gap = n (ขนาดอาเรย์)
2. ลด gap ลงทุกครั้ง: gap = floor(gap / 1.3) (Shrink factor = 1.3)
3. ถ้า gap < 1 ให้ gap = 1 (กลายเป็น Bubble Sort รอบสุดท้าย)
4. เปรียบเทียบ array[i] กับ array[i+gap] สลับถ้าจำเป็น
5. ทำซ้ำจน gap = 1 และไม่มีการสลับ

ตัวอย่างข้อมูล

Input:  108 96 23 74 12 56 85 42 13 47
Output: 12 13 23 42 47 56 74 85 96 108

อัลกอริทึม (Pseudocode)

combSort(array, size)
  gap = size
  flag = true

  while gap != 1 OR flag == true:
    gap = floor(gap / 1.3)
    if gap < 1: gap = 1
    flag = false

    for i = 0 to size - gap - 1:
      if array[i] > array[i + gap]:
        swap(array[i], array[i + gap])
        flag = true

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

#include <iostream>
#include <algorithm>
using namespace std;

void combSort(int *array, int size) {
    int gap = size;
    bool flag = true;

    while (gap != 1 || flag) {
        gap = (gap * 10) / 13;  // gap / 1.3
        if (gap < 1) gap = 1;
        flag = false;

        for (int i = 0; i < size - gap; i++) {
            if (array[i] > array[i + gap]) {
                swap(array[i], array[i + gap]);
                flag = true;
            }
        }
    }
}

void display(int *array, int size) {
    for (int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    combSort(arr, n);
    cout << "After: "; display(arr, n);
}

ทำไม Shrink Factor = 1.3?

ค่า 1.3 มาจากการทดลองเชิงประจักษ์ (Empirical) พบว่าให้ประสิทธิภาพดีที่สุด:

• < 1.3: Gap ลดช้าเกินไป → เหมือน Bubble Sort
• > 1.3: Gap ลดเร็วเกินไป → ข้ามโอกาสแก้ไขการเรียงผิด
• 1.3: สมดุลที่ดีที่สุด

คุณสมบัติ

• In-place: O(1) space
• Not Stable: การสลับแบบ Gap อาจเปลี่ยนลำดับค่าเท่ากัน
• Better than Bubble Sort: แก้ปัญหา "Turtles" (ค่าน้อยอยู่ท้าย)