Counting Sort (การจัดเรียงแบบนับ)

Counting Sort เป็นอัลกอริทึมจัดเรียงแบบ Non-comparison (ไม่เปรียบเทียบ) และ Stable ใช้ได้ดีเมื่อข้อมูลเป็น จำนวนเต็มบวก (Non-negative integers) ในช่วงที่ไม่กว้างเกินไป

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

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

1. หาค่า max ของข้อมูล
2. สร้างอาเรย์ count ขนาด max+1 เริ่มต้นเป็น 0
3. นับความถี่: count[array[i]]++
4. สร้าง Cumulative Frequency: count[i] += count[i-1] (ตำแหน่งสุดท้ายของแต่ละค่า)
5. วางข้อมูลลงอาเรย์ผลลัพธ์จากท้ายไปหัว (เพื่อ Stability)

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

Input:  2 5 6 2 3 10 3 6 7 8
Output: 2 2 3 3 5 6 6 7 8 10

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

countingSort(array, size)
  max = maximum element in array
  count[0..max] = {0}

  for i = 0 to size-1:
    count[array[i]]++

  for i = 1 to max:
    count[i] += count[i-1]  // cumulative

  output[0..size-1]
  for i = size-1 down to 0:
    output[count[array[i]] - 1] = array[i]
    count[array[i]]--

  copy output to array

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

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

int getMax(int *array, int size) {
    int max = array[0];
    for (int i = 1; i < size; i++)
        if (array[i] > max) max = array[i];
    return max;
}

void countSort(int *array, int size) {
    int max = getMax(array, size);
    int *count = new int[max + 1]();
    int *output = new int[size];

    // Count frequencies
    for (int i = 0; i < size; i++)
        count[array[i]]++;

    // Cumulative frequency
    for (int i = 1; i <= max; i++)
        count[i] += count[i-1];

    // Place elements (from end for stability)
    for (int i = size-1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // Copy back
    for (int i = 0; i < size; i++)
        array[i] = output[i];

    delete[] count;
    delete[] output;
}

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);
    countSort(arr, n);
    cout << "After: "; display(arr, n);
}

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

• Stable: รักษาลำดับของค่าเท่ากัน (สำคัญสำหรับ Radix Sort)
• Non-comparison: ไม่เปรียบเทียบค่าโดยตรง
• Linear Time: O(n+k) เร็วกว่า O(n log n) เมื่อ k ไม่ใหญ่

ข้อจำกัด

• ใช้ได้เฉพาะ จำนวนเต็มบวก (Non-negative integers)
• ไม่เหมาะถ้า k (max value) >> n (พื้นที่และเวลามากเกินไป)
• ต้องการพื้นที่ O(n+k) เพิ่มเติม

การประยุกต์ใช้

• เป็น Subroutine ของ Radix Sort
• จัดเรียงคะแนนสอบ, อายุ, รหัสสินค้า ที่มีช่วงจำกัด