Thuật toán Cycle Sort (Sắp xếp chu trình)

Cycle Sort là thuật toán sắp xếp in-place (tại chỗ). Là thuật toán so sánh và hiệu quả hơn các thuật toán in-place khác. Nó tìm số lần ghi bộ nhớ tối thiểu để thực hiện sắp xếp.

Độ phức tạp Cycle Sort

• Time Complexity: O(n²)
• Space Complexity: O(1)

Input và Output

Input: Danh sách chưa sắp xếp: 23 63 98 74 20 14 36 45 99 78
Output: Mảng trước sắp xếp: 23 63 98 74 20 14 36 45 99 78
Mảng sau sắp xếp: 14 20 23 36 45 63 74 78 98 99

Thuật toán

cycleSort(array, size)
Input: Mảng dữ liệu, tổng số phần tử
Output: Mảng đã sắp xếp

Begin
  for start := 0 to n-2 do
    key := array[start]
    location := start
    for i := start+1 to n-1 do
      if array[i] < key then location := location + 1
    done
    if location = start then continue (đúng vị trí, bỏ qua)
    while key = array[location] do location := location + 1 done
    if location ≠ start then swap array[location] with key
    while location ≠ start do
      location := start
      for i := start+1 to n-1 do
        if array[i] < key then location := location + 1
      done
      while key = array[location] do location := location + 1 done
      if key ≠ array[location] then swap array[location] and key
    done
  done
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void swapping(int &a, int &b) { int temp = a; a = b; b = temp; }
void display(int *array, int size) {
    for(int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

void cycleSort(int *array, int n) {
    for(int start = 0; start < n-1; start++) {
        int key = array[start], location = start;
        for(int i = start+1; i < n; i++)
            if(array[i] < key) location++;
        if(location == start) continue;
        while(key == array[location]) location++;
        if(location != start) swapping(array[location], key);
        while(location != start) {
            location = start;
            for(int i = start+1; i < n; i++)
                if(array[i] < key) location++;
            while(key == array[location]) location++;
            if(key != array[location]) swapping(key, array[location]);
        }
    }
}

int main() {
    int n; cout << "Nhập số phần tử: "; cin >> n;
    int arr[n];
    cout << "Nhập phần tử:" << endl;
    for(int i = 0; i < n; i++) cin >> arr[i];
    cout << "Trước sắp xếp: "; display(arr, n);
    cycleSort(arr, n);
    cout << "Sau sắp xếp: "; display(arr, n);
}

Kết quả

Nhập số phần tử: 10
Nhập phần tử: 23 63 98 74 20 14 36 45 99 78
Trước sắp xếp: 23 63 98 74 20 14 36 45 99 78
Sau sắp xếp: 14 20 23 36 45 63 74 78 98 99

Đặc điểm: Cycle Sort giảm thiểu số lần ghi bộ nhớ (memory writes) - tối đa n lần swap. Hữu ích khi ghi bộ nhớ đắt (Flash, EEPROM). Không ổn định.