이 알고리즘은 배열을 가져와 배열의 내용을 섞습니다. 배열 요소의 무작위 순열을 생성합니다.
이 문제를 해결하기 위해 마지막 인덱스에서 시작하여 배열에서 무작위로 생성된 인덱스로 요소를 교환합니다.
입력 및 출력
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)
알고리즘
randomArr(array, n)
입력: 배열, 요소 수.
출력: 배열의 내용을 섞습니다.
Begin for i := n – 1 down to 1, do j := random number from 0 to i swap arr[i] and arr[j] done End
예
#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); }
출력
4 7 8 2 6 3 5 1