Bucket Sort (การจัดเรียงแบบถัง)

Bucket Sort แบ่งข้อมูลเข้า "ถัง" (Buckets) ตามช่วงค่า จัดเรียงในแต่ละถังแยกกัน แล้วรวมกลับมา ใช้ได้ดีเมื่อข้อมูล กระจายอย่างสม่ำเสมอ (Uniformly distributed)

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

Space Complexity: O(n + k) โดย k = จำนวนถัง

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

1. สร้างถัง k ใบ (มัก k = n)
2. แจกแจงข้อมูล: bucket_index = floor(n * value) (สำหรับค่า 0-1) 3. จัดเรียงในแต่ละถัง (ใช้ Insertion Sort หรืออัลกอริทึมอื่น) 4. รวมข้อมูลจากถังทุกใบตามลำดับ

ตัวอย่างข้อมูล (ค่า 0.0 - 1.0)

Input:  0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Output: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79

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

bucketSort(array, size)
  create buckets[0..size-1] as empty lists

  for i = 0 to size-1:
    bucketIndex = floor(size * array[i])
    buckets[bucketIndex].append(array[i])

  for i = 0 to size-1:
    sort(buckets[i])  // ใช้ Insertion Sort หรือ sort()

  index = 0
  for i = 0 to size-1:
    while buckets[i] not empty:
      array[index++] = buckets[i].pop_front()

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

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

void bucketSort(float *array, int size) {
    vector<float> bucket[size];

    // Distribute
    for (int i = 0; i < size; i++) {
        int idx = int(size * array[i]);
        bucket[idx].push_back(array[i]);
    }

    // Sort each bucket
    for (int i = 0; i < size; i++)
        sort(bucket[i].begin(), bucket[i].end());

    // Gather
    int index = 0;
    for (int i = 0; i < size; i++) {
        while (!bucket[i].empty()) {
            array[index++] = bucket[i].front();
            bucket[i].erase(bucket[i].begin());
        }
    }
}

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

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

คุณสมบัติสำคัญ

• Stable: ถ้าอัลกอริทึมจัดเรียงในถังเป็น Stable
• Not In-place: ต้องการพื้นที่สำหรับถัง
• Distribution-dependent: เร็วที่สุดเมื่อข้อมูล Uniform distribution

เมื่อไหร่ควรใช้?

• ข้อมูลเป็น Float/Double ในช่วง [0, 1) หรือแปลงได้
• ข้อมูลกระจายสม่ำเสมอ (Uniform)
• ต้องการ Linear time เฉลี่ย

ข้อควรระวัง

• Worst case O(n²) เมื่อข้อมูลรวมอยู่ในถังเดียว (Skewed distribution)
• ไม่เหมาะกับจำนวนเต็มช่วงกว้าง (ใช้ Radix/Counting Sort ดีกว่า)