Cycle Sort (การจัดเรียงแบบรอบ)

Cycle Sort เป็นอัลกอริทึมจัดเรียงแบบ In-place และ Comparison-based ที่หา จำนวนครั้งการเขียนหน่วยความจำ (Memory Writes) น้อยที่สุด - เหมาะสำหรับหน่วยความจำที่ค่าเขียนแพง (Flash, EEPROM)

ความซับซ้อน (Complexity)

แนวคิดการทำงาน

1. หาตำแหน่งที่ถูกต้องของแต่ละองค์ประกอบ (โดยนับจำนวนค่าที่น้อยกว่า)
2. หากอยู่ที่ถูกต้องแล้ว ข้ามไป
3. หากไม่ใช่: สลับไปยังตำแหน่งที่ถูกต้อง แล้วดำเนินต่อกับค่าที่ถูกสลับมา
4. ทำซ้ำจนครบทุก "Cycle" (รอบ)

ตัวอย่างข้อมูล

Input:  23 63 98 74 20 14 36 45 99 78
Output: 14 20 23 36 45 63 74 78 98 99

อัลกอริทึม (Pseudocode)

cycleSort(array, n)
  for start = 0 to n-2:
    key = array[start]
    location = start

    // หาตำแหน่งที่ถูกต้องของ key
    for i = start+1 to n-1:
      if array[i] < key: location++

    if location == start: continue  // อยู่ที่ถูกต้องแล้ว

    // ข้ามค่าซ้ำ
    while key == array[location]: location++

    // สลับ key เข้าตำแหน่ง
    if location != start:
      swap(array[location], key)

    // ดำเนินต่อจน cycle จบ
    while location != start:
      location = start
      for i = start+1 to n-1:
        if array[i] < key: location++
      while key == array[location]: location++
      if key != array[location]:
        swap(key, array[location])

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

#include <iostream>
#include <algorithm>
using namespace std;

void cycleSort(int *array, int n) {
    for (int start = 0; start < n-1; start++) {
        int key = array[start];
        int 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) swap(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]) swap(key, array[location]);
        }
    }
}

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

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    cycleSort(arr, n);
    cout << "After: "; display(arr, n);
}

คุณสมบัติสำคัญ

• Minimal Writes: แต่ละองค์ประกอบย้ายสูงสุด 1 ครั้ง (Optimal)
• In-place: O(1) extra space
• Not Stable: ไม่รักษาลำดับค่าเท่ากัน
• Not Adaptive: O(n²) เสมอ แม้ข้อมูลเรียงแล้ว

เมื่อไหร่ควรใช้?

• หน่วยความจำที่ "เขียนแพง" (Flash memory, EEPROM, FRAM)
• ระบบฝังตัว (Embedded) ที่ต้องการลดการเขียนหน่วยความจำ
• ไม่เหมาะสำหรับการใช้งานทั่วไป (ช้ากว่า Quick/Merge/Heap Sort)