โปรแกรม C++ สำหรับ Cycle Sort (การเรียงแบบวัฏจักร)

Cycle Sort เป็นอัลกอริทึมการเรียงแบบ in-place, unstable sorting algorithm, comparison sort ที่เหมาะที่สุดในทางทฤษฎีจากมุมมองของจำนวนการเขียน (writes) ลงอาร์เรย์ต้นฉบับ นี่แตกต่างจากอัลกอริทึมเรียง in-place ทุกตัวอย่าง มันอิงตามแนวคิดว่า permutation ที่ต้องการเรียงสามารถแยกเป็น cycles ได้ ซึ่งแต่ละ cycle สามารถหมุนเวียนได้เพื่อให้ผลลัพธ์ที่เรียงแล้ว

ไม่เหมือนการเรียงทุกตัวอื่น องค์ประกอบไม่เคยถูกเขียนที่อื่นในอาร์เรย์เพื่อผลักให้หลุดจากทาง แต่แต่ละค่าจะถูกเขียนศูนย์ครั้ง (ถ้าอยู่ตำแหน่งถูกต้องแล้ว) หรือหนึ่งครั้งไปยังตำแหน่งที่ถูกต้อง ซึ่งตรงกับจำนวนการเขียนทับน้อยที่สุดที่จำเป็นสำหรับการเรียง in-place ให้เสร็จสมบูรณ์

การลดจำนวนการเขียนมีประโยชน์เมื่อการเขียนข้อมูลชุดใหญ่มีค่าใช้จ่ายสูงมาก เช่น EEPROMs หรือ Flash memory ที่แต่ละครั้งที่เขียนจะลดอายุการใช้งานของหน่วยความจำ

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

คำอธิบาย

arr[] = {10, 5, 2, 3} index = 0 1 2 3
cycle_start = 0, item = 10 = arr[0]
หาตำแหน่งที่จะวาง item, pos = cycle_start
while (arr[i] < item) pos++;
วาง 10 ที่ arr[3] เปลี่ยน item เป็นค่าเก่าของ arr[3]
arr[] = {10, 5, 2, 10} item = 3
หมุน cycle ที่เหลือเริ่ม index '0'
หาตำแหน่ง item = 3 สลับ item กับ arr[1] arr[] = {10, 3, 2, 10} item = 5
หมุน cycle ที่เหลือเริ่ม index '0' item = 5 สลับกับ arr[2] arr[] = {10, 3, 5, 10} item = 2
หมุน cycle ที่เหลือเริ่ม index '0' item = 2 arr[] = {2, 3, 5, 10}
ข้างต้นเป็นหนึ่งรอบสำหรับ cycle_start = 0 ทำซ้ำสำหรับ cycle_start = 1, 2, ..n-2

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

#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;
}