Chương trình C++ sắp xếp nhỏ hơn 100 số với độ phức tạp O(n)

Để sắp xếp một số lượng nhỏ các số trong thời gian tuyến tính, chúng ta có thể sử dụng kỹ thuật sắp xếp đếm (counting sort).

Counting sort là một kỹ thuật sắp xếp ổn định (stable), được dùng để sắp xếp các đối tượng theo các khóa (keys) là các số nhỏ. Nó đếm số lượng khóa có giá trị khóa giống nhau. Kỹ thuật sắp xếp này hiệu quả khi sự khác biệt giữa các khóa khác nhau không quá lớn, ngược lại nó có thể tăng độ phức tạp không gian.

Độ phức tạp của Counting Sort

• Độ phức tạp thời gian: O(n + r)

• Độ phức tạp không gian: O(n + r)

Đầu vào - Danh sách dữ liệu không sắp xếp: 2 5 6 2 3 10 3 6 7 8 
Đầu ra - Mảng sau khi sắp xếp: 2 2 3 3 5 6 6 7 8 10

Thuật toán

countingSort(array, size)

Đầu vào - Một mảng dữ liệu, và tổng số trong mảng

Đầu ra - Mảng đã sắp xếp

Bắt đầu
    max = lấy phần tử lớn nhất từ mảng.
    Định nghĩa mảng count kích thước [max+1]
    Với i := 0 đến max thực hiện
        count[i] = 0 //đặt tất cả phần tử trong mảng count = 0
    Kết thúc
    Với i := 1 đến size thực hiện
        Tăng count của mỗi số tìm thấy trong mảng
    Kết thúc
    Với i := 1 đến max thực hiện
        count[i] = count[i] + count[i + 1] //tìm tần suất tích lũy
    Kết thúc
    Với i := size đến 1 giảm 1 thực hiện
        Lưu số vào mảng đầu ra
        Giảm count[i]
    Kết thúc
    Trả về mảng đầu ra
Kết thúc

Mã ví dụ

#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 << "Nhập kích thước mảng: "; 
    cin >> num; 
    cout << "Nhập " << num << " phần tử cần sắp xếp:" << endl; 
    for (i = 0; i < num; i++) 
        cin >> array[i]; 
    cout << "\nMảng trước khi sắp xếp: " << endl; 
    for (i = 0; i < num; i++) 
        cout << array[i] << " "; 
    cout << "\nMảng sau khi sắp xếp: " << endl; 
    counting_sort(array, num); 
    for (i = 0; i < num; i++) 
        cout << array[i] << " "; 
    return 0; 
}

Kết quả

Nhập kích thước mảng: 8 
Nhập 8 phần tử cần sắp xếp: 
54 89 23 20 18 88 65 31 
Mảng trước khi sắp xếp: 
54 89 23 20 18 88 65 31 
Mảng sau khi sắp xếp: 
54 89 23 20 18 88 65 31