Add Exchange Sort (TheAlgorithms#301)

NilsFa1 · web-flow · commit 906dfaad5636 · 2022-04-05T16:45:11.000+03:00
diff --git a/Algorithms.Tests/Sorters/Comparison/ExchangeSorterTests.cs b/Algorithms.Tests/Sorters/Comparison/ExchangeSorterTests.cs
@@ -0,0 +1,28 @@
+﻿using System;
+using Algorithms.Sorters.Comparison;
+using Algorithms.Tests.Helpers;
+using NUnit.Framework;
+
+namespace Algorithms.Tests.Sorters.Comparison
+{
+    public static class ExchangeSorterTests
+    {
+        [Test]
+        public static void ArraySorted(
+            [Random(0, 1000, 100, Distinct = true)]
+            int n)
+        {
+            // Arrange
+            var sorter = new ExchangeSorter<int>();
+            var intComparer = new IntComparer();
+            var (correctArray, testArray) = RandomHelper.GetArrays(n);
+
+            // Act
+            sorter.Sort(testArray, intComparer);
+            Array.Sort(correctArray, intComparer);
+
+            // Assert
+            Assert.AreEqual(testArray, correctArray);
+        }
+    }
+}
diff --git a/Algorithms/Sorters/Comparison/ExchangeSorter.cs b/Algorithms/Sorters/Comparison/ExchangeSorter.cs
@@ -0,0 +1,34 @@
+﻿using System.Collections.Generic;
+
+namespace Algorithms.Sorters.Comparison
+{
+    /// <summary>
+    ///     Class that implements exchange sort algorithm.
+    /// </summary>
+    /// <typeparam name="T">Type of array element.</typeparam>
+    public class ExchangeSorter<T> : IComparisonSorter<T>
+    {
+        /// <summary>
+        ///     Sorts array using specified comparer,
+        ///     internal, in-place, stable,
+        ///     time complexity: O(n^2),
+        ///     space complexity: O(1),
+        ///     where n - array length.
+        /// </summary>
+        /// <param name="array">Array to sort.</param>
+        /// <param name="comparer">Compares elements.</param>
+        public void Sort(T[] array, IComparer<T> comparer)
+        {
+            for (var i = 0; i < array.Length - 1; i++)
+            {
+                for (var j = i + 1; j < array.Length; j++)
+                {
+                    if (comparer.Compare(array[i], array[j]) > 0)
+                    {
+                        (array[j], array[i]) = (array[i], array[j]);
+                    }
+                }
+            }
+        }
+    }
+}
diff --git a/README.md b/README.md
@@ -71,6 +71,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)
+      * [Exchange Sort](./Algorithms/Sorters/Comparison/ExchangeSorter.cs)
       * [Heap Sort](./Algorithms/Sorters/Comparison/HeapSorter.cs)
       * [Insertion Sort](./Algorithms/Sorters/Comparison/InsertionSorter.cs)
       * [Merge Sort](./Algorithms/Sorters/Comparison/MergeSorter.cs)
