โปรแกรม C++ อัลกอริทึม Counting Sort

Counting Sort

Counting sort เป็นเทคนิคการจัดเรียงที่เสถียร (stable sorting technique) ใช้จัดเรียงวัตถุตามกุญแจ (keys) ที่เป็นตัวเลขน้อย นับจำนวนกุญแจที่มีค่ากุญแจเท่ากัน เทคนิคการจัดเรียงนี้มีประสิทธิภาพเมื่อความแตกต่างระหว่างกุญแจต่างๆ ไม่มากนัก มิฉะนั้นอาจเพิ่มความซับซ้อนของพื้นที่ (space complexity)

ความซับซ้อนของ Counting Sort

• Time Complexity: O(n+r)

• Space Complexity: O(n+r)

Input - รายการข้อมูลที่ไม่ได้จัดเรียง: 2 5 6 2 3 10 3 6 7 8

Output - อาร์เรย์หลังจัดเรียง: 2 2 3 3 5 6 6 7 8 10

อัลกอริทึม

countingSort(array, size)

Input: อาร์เรย์ข้อมูล, และจำนวนรวมในอาร์เรย์

Output: อาร์เรย์ที่จัดเรียงแล้ว

เริ่มต้น
  max = หาองค์ประกอบสูงสุดจากอาร์เรย์
  ประกาศอาร์เรย์ count ขนาด [max+1]
  for i := 0 ถึง max
    count[i] = 0 // ตั้งค่าทุกองค์ประกอบในอาร์เรย์ count เป็น 0
  for i := 1 ถึง size
    เพิ่มจำนวนนับของแต่ละตัวเลขที่พบในอาร์เรย์
  for i := 1 ถึง max
    count[i] = count[i] + count[i+1] // หาความถี่สะสม (cumulative frequency)
  for i := size ถึง 1 ลดลงทีละ 1
    เก็บตัวเลขในอาร์เรย์ผลลัพธ์
    ลด count[i]
  คืนค่าอาร์เรย์ผลลัพธ์
สิ้นสุด

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

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

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

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

void countSort(int *array, int size) {
    int output[size+1];
    int max = getMax(array, size);
    int count[max+1];
    for(int i = 0; i <= max; i++)
        count[i] = 0;
    for(int i = 1; i <= size; i++)
        count[array[i]]++;
    for(int i = 1; i <= max; i++)
        count[i] += count[i-1];
    for(int i = size; i >= 1; i--) {
        output[count[array[i]]] = array[i];
        count[array[i]] -= 1;
    }
    for(int i = 1; i <= size; i++) {
        array[i] = output[i];
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n+1];
    cout << "Enter elements:" << endl;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    countSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

ผลลัพธ์ตัวอย่าง

Enter the number of elements: 10
Enter elements: 2 5 6 2 3 10 3 6 7 8
Array before Sorting: 2 5 6 2 3 10 3 6 7 8
Array after Sorting: 2 2 3 3 5 6 6 7 8 10