Shuffle Array Contents (การสุ่มลำดับอาร์เรย์): อัลกอริทึม Fisher-Yates

อัลกอริทึมนี้รับอาร์เรย์และสุ่มลำดับสมาชิก (Shuffle) สร้างการเรียงสับเปลี่ยนแบบสุ่ม (Random Permutation)

วิธีแก้: สลับสมาชิกเริ่มจากดัชนีสุดท้ายไปยังดัชนีสุ่มในอาร์เรย์

Input และ Output

Input: อาร์เรย์จำนวนเต็ม: {1, 2, 3, 4, 5, 6, 7, 8}
Output: ผลลัพธ์สุ่ม: 3 4 7 2 6 1 5 8 (แต่ละครั้งรันผลลัพธ์ต่างกัน)

Algorithm

randomArr(array, n)

Input: อาร์เรย์, จำนวนสมาชิก

Output: สลับลำดับสมาชิกในอาร์เรย์

Begin
    for i := n-1 down to 1 do
        j := random number from 0 to i
        swap arr[i] and arr[j]
    done
End

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

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

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

void randomArr(int arr[], int n) {
    srand(time(NULL)); // ใช้เวลาเป็น seed เพื่อค่าสุ่มต่างกันทุกครั้ง
    for (int i = n-1; i > 0; i--) {
        int j = rand() % (i+1); // สุ่มดัชนี 0 ถึง i
        swap(arr[i], arr[j]);   // สลับสมาชิกปัจจุบันกับตำแหน่ง j
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = 8;
    randomArr(arr, n);
    display(arr, n);
}

Output

4 7 8 2 6 3 5 1