Fisher-Yates shuffle algorithm in C++
Fisher-Yates shuffle is a popular algorithm used for shuffling elements in an array or a list. The algorithm was first described by Ronald Fisher and Frank Yates in their book "Statistical tables for biological, agricultural and medical research" in 1938. The Fisher-Yates shuffle algorithm is a simple and efficient algorithm that can be used to generate random permutations of a given array or list.
The basic idea behind the Fisher-Yates shuffle algorithm is to iterate through the array or list from the last element to the first element. For each element, generate a random index between the current and the last index. The element at the current index is then swapped with the element at the randomly generated index. This process is repeated for all the elements in the array or list, resulting in a completely random permutation of the elements.
The Fisher-Yates shuffle algorithm can be implemented in C++ using the following steps:
- Initialize a variable 'n' to the length of the array or list.
- Iterate through the array or list from the last element to the first element.
- For each element, generate a random index between the current index and the last index.
- Swap the element at the current index with the element at the randomly generated index.
- Repeat steps 2-4 for all the elements in the array or list.
Example:
Here is an example of the Fisher-Yates shuffle algorithm implemented in C++:
#include <iostream>
#include <cstdlib>
void fisher_yates_shuffle(int arr[], int n) {
// Iterate through the array from the last element to the first element
for (int i = n - 1; i> 0; i--) {
// Generate a random index between the current index and the last index
int j = rand() % (i + 1);
// Swap the element at the current index with the element at the randomly generated index
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
std::cout<< "Original array: ";
for (int i = 0; i< n; i++) {
std::cout<<arr[i] << " ";
}
std::cout<< std::endl;
fisher_yates_shuffle(arr, n);
std::cout<< "Shuffled array: ";
for (int i = 0; i< n; i++) {
std::cout<<arr[i] << " ";
}
std::cout<< std::endl;
return 0;
}
Output:
Original array: 1 2 3 4 5 6 7 8 9 10
Shuffled array: 9 3 6 2 8 1 5 7 4 10
In this example, the fisher_yates_shuffle() function takes an array 'arr' and an integer 'n' as its arguments. The function iterates through the array from the last element to the first element, and for each element, generates a random index between the current index and the last index. The element at the current index is then swapped with the element at the randomly generated index.
In the main() function, an array 'arr' of integers is defined, and the length of the array is stored in the variable 'n'. The original array is printed to the console using a for loop, and then the fisher_yates_shuffle() function is called with the array and its length as arguments. After the function is called, the shuffled array is printed to the console using another for loop.
As we can see, the original array has been shuffled and the elements are in a completely different order. The Fisher-Yates shuffle algorithm ensures that every permutation of the elements is equally possible, so the output will be different every time the program is run.
Conclusion
In conclusion, the Fisher-Yates shuffle algorithm is a simple and efficient algorithm that can be used to generate random permutations of a given array or list. The Fisher-Yates shuffle algorithm is an in-place algorithm, which makes it a very efficient solution for shuffling elements in an array or list.