Add Fisher-Yates Shuffle Algorithm (TheAlgorithms#281)

Dima1247 · DPalaSS · siriak · web-flow · commit 67abf367dde5 · 2022-01-23T20:48:10.000+02:00
Co-authored-by: Dmytro Palamarchuk &lt;dpala@softserveinc.com&gt;
Co-authored-by: Andrii Siriak &lt;siryaka@gmail.com&gt;
diff --git a/Algorithms.Tests/Shufflers/FisherYatesShufflerTests.cs b/Algorithms.Tests/Shufflers/FisherYatesShufflerTests.cs
@@ -0,0 +1,45 @@
+using Algorithms.Shufflers;
+using Algorithms.Tests.Helpers;
+using FluentAssertions;
+using NUnit.Framework;
+using System;
+
+namespace Algorithms.Tests.Shufflers
+{
+    public static class FisherYatesShufflerTests
+    {
+        [Test]
+        public static void ArrayShuffled_NewArrayHasSameSize(
+            [Random(0, 1000, 100, Distinct = true)]
+            int n)
+        {
+            // Arrange
+            var shuffler = new FisherYatesShuffler<int>();
+            var (correctArray, testArray) = RandomHelper.GetArrays(n);
+
+            // Act
+            shuffler.Shuffle(testArray);
+
+            // Assert
+            testArray.Length.Should().Be(correctArray.Length);
+        }
+
+        [Test]
+        public static void ArrayShuffled_NewArrayHasSameValues(
+            [Random(0, 1000, 100, Distinct = true)]
+            int n)
+        {
+            // Arrange
+            var shuffler = new FisherYatesShuffler<int>();
+            var (correctArray, testArray) = RandomHelper.GetArrays(n);
+
+            // Act
+            shuffler.Shuffle(testArray);
+            Array.Sort(testArray);
+            Array.Sort(correctArray);
+
+            // Assert
+            testArray.Should().BeEquivalentTo(correctArray);
+        }
+    }
+}
diff --git a/Algorithms/Algorithms.csproj b/Algorithms/Algorithms.csproj
@@ -1,4 +1,4 @@
-﻿<Project Sdk="Microsoft.NET.Sdk">
+<Project Sdk="Microsoft.NET.Sdk">
 
   <PropertyGroup>
     <TargetFramework>net5.0</TargetFramework>
diff --git a/Algorithms/Shufflers/FisherYatesShuffler.cs b/Algorithms/Shufflers/FisherYatesShuffler.cs
@@ -0,0 +1,31 @@
+using System;
+
+namespace Algorithms.Shufflers
+{
+    /// <summary>
+    ///     Fisher-Yates shuffle is a simple shuffling algorithm,
+    ///     which is usually used to shuffle a deck of cards.
+    /// </summary>
+    /// <typeparam name="T">Type array input.</typeparam>
+    public class FisherYatesShuffler<T> : IShuffler<T>
+    {
+        /// <summary>
+        ///     Shuffles input array using Fisher-Yates algorithm.
+        ///     The algorithm starts shuffling from the last element
+        ///     and swap elements one by one. We use random index to
+        ///     choose element we use in swap operation.
+        /// </summary>
+        /// <param name="array">Array to shuffle.</param>
+        public void Shuffle(T[] array)
+        {
+            var random = new Random();
+
+            for (var i = array.Length - 1; i > 0; i--)
+            {
+                var j = random.Next(0, i + 1);
+
+                (array[i], array[j]) = (array[j], array[i]);
+            }
+        }
+    }
+}
diff --git a/Algorithms/Shufflers/IShuffler.cs b/Algorithms/Shufflers/IShuffler.cs
@@ -0,0 +1,15 @@
+namespace Algorithms.Shufflers
+{
+    /// <summary>
+    ///     Shuffles array.
+    /// </summary>
+    /// <typeparam name="T">Type of array item.</typeparam>
+    public interface IShuffler<in T>
+    {
+        /// <summary>
+        ///     Shuffles array.
+        /// </summary>
+        /// <param name="array">Array to Shuffle.</param>
+        void Shuffle(T[] array);
+    }
+}
diff --git a/README.md b/README.md
@@ -70,6 +70,7 @@ This repository contains algorithms and data structures implemented in C# for ed
       * [Cocktail Sort](./Algorithms/Sorters/Comparison/CocktailSorter.cs)
       * [Comb Sort](./Algorithms/Sorters/Comparison/CombSorter.cs)
       * [Cycle Sort](./Algorithms/Sorters/Comparison/CycleSorter.cs)
+      * [Fisher-Yates Shuffle](./Algorithms/Sorters/Comparison/FisherYatesShuffler.cs)
       * [Heap Sort](./Algorithms/Sorters/Comparison/HeapSorter.cs)
       * [Insertion Sort](./Algorithms/Sorters/Comparison/InsertionSorter.cs)
       * [Merge Sort](./Algorithms/Sorters/Comparison/MergeSorter.cs)

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,4 @@`
`1`		`-<Project Sdk="Microsoft.NET.Sdk">`
	`1`	`+<Project Sdk="Microsoft.NET.Sdk">`
`2`	`2`
`3`	`3`	`<PropertyGroup>`
`4`	`4`	`<TargetFramework>net5.0</TargetFramework>`