Chương trình C++ thuật toán Cycle Sort

Cycle Sort là thuật toán sắp xếp tại chỗ (in-place), không ổn định (unstable), sắp xếp bằng so sánh, tối ưu về mặt lý thuyết về tổng số lần ghi vào mảng gốc, khác với mọi thuật toán sắp xếp tại chỗ khác. Nó dựa trên ý tưởng rằng hoán vị cần sắp xếp có thể phân tích thành các chu trình (cycles), mỗi chu trình có thể xoay riêng để cho kết quả đã sắp xếp.

Khác với hầu hết các thuật toán sắp xếp khác, các phần tử không bao giờ được ghi ở nơi khác trong mảng chỉ để nhường chỗ. Mỗi giá trị hoặc được ghi 0 lần (nếu đã ở đúng vị trí) hoặc ghi 1 lần vào vị trí đúng. Điều này khớp với số lần ghi đè tối thiểu cho sắp xếp tại chỗ hoàn chỉnh.

Giảm thiểu số lần ghi hữu ích khi ghi vào tập dữ liệu lớn rất tốn kém, như EEPROM/Flash memory nơi mỗi lần ghi giảm tuổi thọ bộ nhớ.

Ví dụ

Input: a[] = {7, 4, 3, 5, 2, 1, 6} 
Output: 1 2 3 4 5 6 7

Giải thích

arr[] = {10, 5, 2, 3} 
index = 0 1 2 3 
cycle_start = 0 
item = 10 = arr[0] 
Tìm vị trí đặt item, pos = cycle_start 
while (arr[i] < item) pos++; 
Đặt 10 tại arr[3], item = giá trị cũ arr[3] 
arr[] = {10, 5, 2, 10}, item = 3 
Xoay tiếp chu trình từ index 0, item = 3, hoán vị với arr[1] 
arr[] = {10, 3, 2, 10}, item = 5 
Tiếp tục... cuối cùng arr[] = {2, 3, 5, 10} 
Lặp lại cho cycle_start = 1, 2, ... n-2

Ví dụ mã C++

#include <iostream> 
using namespace std; 

void cycleSort(int a[], int n) { 
    int writes = 0; 
    for (int c_start = 0; c_start <= n - 2; c_start++) { 
        int item = a[c_start]; 
        int pos = c_start; 
        for (int i = c_start + 1; i < n; i++) 
            if (a[i] < item) pos++; 
        if (pos == c_start) continue; 
        while (item == a[pos]) pos += 1; 
        if (pos != c_start) { 
            swap(item, a[pos]); 
            writes++; 
        } 
        while (pos != c_start) { 
            pos = c_start; 
            for (int i = c_start + 1; i < n; i++) 
                if (a[i] < item) pos += 1; 
            while (item == a[pos]) pos += 1; 
            if (item != a[pos]) { 
                swap(item, a[pos]); 
                writes++; 
            } 
        } 
    } 
} 

int main() { 
    int a[] = {7, 4, 3, 5, 2, 1, 6}; 
    int n = 7; 
    cycleSort(a, n); 
    for (int i = 0; i < n; i++) 
        cout << a[i] << " "; 
    return 0; 
}