fisher yates Algorithm
The Fisher-Yates algorithm, also known as the Knuth shuffle, is a popular and efficient method for generating a random permutation of a finite sequence. The algorithm was originally designed by Ronald Fisher and Frank Yates in 1938 and later improved by Donald Knuth in 1964. The primary purpose of this algorithm is to shuffle an array of elements in such a way that every possible permutation of the input sequence has an equal probability of occurrence. This unbiased shuffling ensures the randomness of the output, which is particularly useful in applications such as simulations, cryptography, and gaming.
The Fisher-Yates algorithm works by iterating through the array of elements from the last index to the first, selecting a random index less than or equal to the current index, and then swapping the elements at these two indices. This process is repeated until the entire array has been traversed, resulting in a randomly shuffled output. The algorithm has a time complexity of O(n), where n is the number of elements in the array, making it an efficient and scalable solution for shuffling large datasets. Furthermore, by leveraging in-place swapping, the Fisher-Yates algorithm eliminates the need for any additional memory, resulting in a space complexity of O(1).
# Fisher and Yates Shuffle is one of the simplest and most popular shuffling algorithm
def fisher_yates_shuffle(array)
n = array.length
while n > 0
i = rand(n-=1)
array[i], array[n] = array[n], array[i]
end
return array
end
arr = [1, 2, 40, 30, 20, 15, 323, 12, 3, 4]
puts fisher_yates_shuffle(arr)
