Fisher–Yates shuffle Algorithm c++

The Fisher-Yates shuffle algorithm is a commonly used algorithm for shuffling the elements of an array randomly. It works by iterating through the array from the last element to the first, and at each iteration, it selects a random index from the remaining unshuffled elements and swaps it with the current element. This process is repeated until all elements have been shuffled.

Here is a step-by-step explanation of the Fisher-Yates shuffle algorithm in C++:

  1. Start by initializing an array of elements that you want to shuffle. Let's call it "arr" and assume it has "n" elements.

  2. Iterate through the array from the last element to the first. In C++, this can be done using a for loop with the loop variable "i" initialized to "n-1" and decremented by 1 in each iteration until it reaches 0.

  3. Within each iteration, generate a random index "j" between 0 and "i" (inclusive). This index will be used to select a random unshuffled element from the remaining unshuffled elements.

  4. Swap the element at index "i" with the element at index "j". This step ensures that the current element at index "i" is now part of the shuffled portion of the array, and the element at index "j" is now unshuffled.

  5. Repeat steps 3 and 4 until all elements have been shuffled. This means that the loop in step 2 will run "n" times.

  6. After the loop completes, the array "arr" will contain the shuffled elements.

Here is an example implementation of the Fisher-Yates shuffle algorithm in C++:

#include <iostream>
#include <cstdlib>
#include <ctime>

void fisherYatesShuffle(int arr[], int n) {
    // Seed the random number generator
    std::srand(std::time(nullptr));

    for (int i = n - 1; i > 0; --i) {
        // Generate a random index between 0 and i (inclusive)
        int j = std::rand() % (i + 1);

        // Swap arr[i] with arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    fisherYatesShuffle(arr, n);

    std::cout << "Shuffled array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

This example demonstrates how to shuffle an array of integers using the Fisher-Yates shuffle algorithm in C++. The fisherYatesShuffle function takes an array arr and its size n as parameters and shuffles the elements in-place. The shuffled array is then printed using a simple for loop in the main function.

I hope this explanation helps! Let me know if you have any further questions.