โปรแกรม C++ เรียงตัวเลขน้อยกว่า 100 ด้วย Counting Sort O(n)

เพื่อเรียงตัวเลขเล็กๆ ในเวลาเชิงเส้น เราสามารถใช้เทคนิค Counting Sort

Counting Sort เป็นการเรียงลำดับที่เสถียร (stable) ใช้เรียงวัตถุตามคีย์ที่เป็นตัวเลขน้อย นับจำนวนคีย์ที่มีค่าเท่ากัน เทคนิคนี้มีประสิทธิภาพเมื่อความต่างระหว่างคีย์ต่างๆ ไม่มาก มิฉะนั้นอาจเพิ่ม 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: อาร์เรย์ที่เรียงแล้ว

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

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

#include <iostream>
using namespace std;

void counting_sort(int array[], int n) {
    int i, j;
    int count[n];
    for (i = 0; i < n; i++)
        count[i] = 0;
    for (i = 0; i < n; i++)
        (count[array[i]])++;
    for (i = 0, j = 0; i < n; i++)
        for (; count[i] > 0; (count[i])--)
            array[j++] = i;
}

int main() {
    int array[100], i, num;
    cout << "Enter the size of array : ";
    cin >> num;
    cout << "Enter the " << num << " elements to be sorted:" << endl;
    for (i = 0; i < num; i++)
        cin >> array[i];
    cout << "\nThe array of elements before sorting : " <<endl;
    for (i = 0; i < num; i++)
        cout << array[i] << " ";
    cout << "\nThe array of elements after sorting : " << endl;
    counting_sort(array, num);
    for (i = 0; i < num; i++)
        cout << array[i] << " ";
    return 0;
}

ผลลัพธ์

Enter the size of array : 8
Enter the 8 elements to be sorted: 54 89 23 20 18 88 65 31
The array of elements before sorting : 54 89 23 20 18 88 65 31
The array of elements after sorting : 54 89 23 20 18 88 65 31