Xáo trộn nội dung mảng (Shuffle Array Contents)

Thuật toán này nhận một mảng và xáo trộn nội dung của mảng. Nó tạo ra một hoán vị ngẫu nhiên của các phần tử mảng.

Để giải quyết, ta hoán đổi các phần tử bắt đầu từ chỉ mục cuối về chỉ mục ngẫu nhiên trong mảng.

Đầu vào và Đầu ra

Đầu vào: Mảng số nguyên: {1, 2, 3, 4, 5, 6, 7, 8}
Đầu ra: Xáo trộn mảng: 3 4 7 2 6 1 5 8 (Kết quả có thể khác mỗi lần chạy)

Thuật toán

randomArr(array, n)

Đầu vào: Mảng, số phần tử.

Đầu ra: Xáo trộn nội dung mảng.

Begin
    for i := n – 1 down to 1, do
        j := số ngẫu nhiên từ 0 đến i
        hoán đổi arr[i] và arr[j]
    done
End

Ví dụ (C++)

#include 
#include 
#include 
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));
    for (int i = n-1; i > 0; i--) {
        int j = rand() % (i+1);
        swap(arr[i], arr[j]);
    }
}
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = 8;
    randomArr(arr, n);
    display(arr, n);
}

Đầu ra

4 7 8 2 6 3 5 1