Trộn nội dung mảng

Thuật toán này sẽ lấy một mảng và xáo trộn nội dung của mảng. Nó sẽ 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 vấn đề này, chúng tôi sẽ hoán đổi các phần tử bắt đầu từ chỉ mục cuối cùng thành một chỉ mục được tạo ngẫu nhiên trong mảng.

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

Input:
An array of integers: {1, 2, 3, 4, 5, 6, 7, 8}
Output:
Shuffle of array contents: 3 4 7 2 6 1 5 8 (Output may differ for next run)

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 của mảng.

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

Ví dụ

#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 ) {           //generate random array element
   srand (time(NULL));                 //use time to get different seed value to start
   for (int i = n-1; i > 0; i--) {
      int j = rand() % (i+1);           //randomly choose an index from 0 to i
      swap(arr[i], arr[j]);            //swap current element with element placed in jth location
   }
}

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