โปรแกรม C++ ใช้ Fisher-Yates Algorithm สลับลำดับอาร์เรย์ (Array Shuffling)

Fisher-Yates Algorithm (หรือที่รู้จักในชื่อ Knuth Shuffle) เป็นอัลกอริทึมที่สร้างการจัดเรียงแบบสุ่ม (random permutation) ของสมาชิกในอาร์เรย์ ทุกการจัดเรียงที่เป็นไปได้มีโอกาสเท่ากัน (unbiased)

โค้ดโปรแกรม Fisher-Yates Shuffle

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    int n;
    cout << "Enter the array size: ";
    cin >> n;
    
    int arr[n], shuffled[n];
    
    cout << "Enter the array elements: ";
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    // เริ่มต้น random seed
    srand(time(0));
    
    // Fisher-Yates Shuffle (เวอร์ชันที่ถูกต้อง)
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);  // สุ่ม index 0 ถึง i
        swap(arr[i], arr[j]);      // สลับตำแหน่ง
    }
    
    cout << "The shuffled array is: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the array size: 10
Enter the array elements: 1 2 3 4 5 6 7 8 9 10
The shuffled array is: 4 7 8 6 3 10 2 1 9 5

หลักการทำงานของ Fisher-Yates (เวอร์ชันสมัยใหม่)

1. เริ่มจากท้ายอาร์เรย์ (index n-1) ไปจนถึง index 1
2. สุ่ม index j ระหว่าง 0 ถึง i (รวม)
3. สลับ arr[i] กับ arr[j]
4. ทำซ้ำจนครบทุกตัว

ข้อดีของเวอร์ชันนี้:

• In-place: ไม่ต้องใช้อาร์เรย์เพิ่มเติม
• O(n) time complexity: วนลูปเพียง n-1 รอบ
• Unbiased: ทุก permutation โอกาสเท่ากัน

หมายเหตุสำคัญ

โค้ดต้นฉบับในบทความใช้วิธี index_arr ตรวจสอบ index ที่สุ่มแล้ว ซึ่งทำงานได้แต่ไม่มีประสิทธิภาพ (อาจลูปวนนานหากสุ่มชนกัน) วิธี Fisher-Yates แบบมาตรฐานข้างต้นแนะนำให้ใช้แทน