Sorting is one of the most common problems that programmers solve while building applications. Selection sort is one of the algorithms that we can use to sort elements in an array. We are going to learn how to implement selection sort in C# and analyze how the algorithm performs when sorting arrays of various sizes.<\/p>\n
Let’s start.\u00a0<\/p>\n
The goal of the selection sort algorithm is to find the minimum value of an array by iterating through each element. For each iteration, the algorithm compares the current minimum value of the array with the current element. If the current value is smaller than the minimum value, a swap process occurs. This process continues until the array is completely sorted.<\/p>\n
Let’s learn how selection sort in C# works and understand its time and space complexity.\u00a0<\/p>\n
Let’s assume we have an array of five numbers we need to sort in ascending order: First, we find the minimum value from elements 0 to 4 (indexes) and place it at position 0. The minimum value is 10. Since 40 is currently on position 0 we are going to swap it with 10: Then, we check the elements 1 through 4 and place the smallest value at position 1. In this case, 20 is the minimum and we swap it with 40: Next, we check positions 2 through 4 and set the minimum value (30) to position 2: Let’s learn how to implement Selection Sort in C#.\u00a0<\/p>\n First, we are going to define an array property As the next step, we are going to create a We can see that the algorithm uses two nested loops during the sorting process. We define two variables\u00a0( If the value of the array element is smaller than the current minimum value, swapping occurs. This process stops when the outer loop hits its We can go ahead to verify that the method returns a sorted array:\u00a0<\/p>\n For each iteration, the smallest value and the current value swap their positions. To accomplish this, the algorithm uses nested loops to compare array elements.\u00a0<\/p>\n As the length of the array increases to N, the time complexity would be O(N\u00b2) because we use two nested loops. The algorithm has a space complexity of O(1) as the sorting process doesn’t need an extra array to store the final result.\u00a0<\/p>\n Best Case Complexity:\u00a0<\/strong>it occurs when we need to sort a sorted array. The algorithm would need to perform comparisons without swapping values.\u00a0<\/p>\n Average Case Complexity: <\/strong>this scenario occurs when a mix of both sorted and unsorted values needs to be sorted in ascending order. The algorithm would need to perform comparisons while swapping some values.<\/p>\n Worst Case Complexity: <\/strong>assuming we have a list of numbers that are in descending order and we need to sort them in ascending order, the algorithm would encounter a worst-case complexity as the length of that array grows to N. Therefore, the algorithm compares while swapping all the values.<\/p>\n Selection sort is ideal for sorting values that do not occupy a lot of memory<\/strong>. As the length of the array increases, the time taken to sort it increases exponentially as the algorithm has a time complexity of O(N\u00b2).\u00a0<\/p>\n We can use this algorithm when the cost of swapping values doesn’t matter<\/strong>. For example, if the computing resources we need to swap those values are minimal, we could consider using this algorithm.<\/p>\n Ideal for situations where the cost of writing to a disk space matters<\/strong>. For example, a flash disk with no extra space could work with this algorithm as opposed to a sorting algorithm such as bubble sort<\/a> that has a space complexity of O(N\u00b2).<\/p>\n We should not use selection sort in a sorted array<\/strong>, as it would still perform O(N\u00b2) comparisons. In such a scenario, a sorting algorithm such as bubble sort would perform those comparisons in one iteration.<\/p>\n Selection sort becomes inefficient as the size of the array grows<\/strong>. Using this algorithm in CPU-intensive applications could reduce their performance.\u00a0<\/p>\n Let’s verify that the selection sort algorithm has a time complexity of O(N\u00b2) by using performance benchmarks to test how long the algorithm takes to sort an array.<\/p>\n To kickstart this process, we are going to define a method that generates random numbers and adds them to an array with a specific length:<\/p>\n The To simulate a scenario where we have an array that is in order, we are going to define a method Next, we are going to run a benchmark to understand how the algorithm performs when sorting arrays that have random elements:<\/p>\n We define three array objects of different sizes (to simulate time complexity scenarios) that hold random numbers<\/a> from the
\nint[] array = { 40, 10, 20, 30, 50 };<\/code><\/p>\n
\n10<\/span>, 40<\/span>, 20, 30, 50<\/code><\/p>\n
\n10, 20<\/span>, 40<\/span>, 30, 50<\/code><\/p>\n
\n10, 20, 30<\/span>, 40<\/span>, 50<\/code><\/p>\n<\/a>How to Implement Selection Sort in C#?<\/h2>\n
NumArray<\/code> that we are going to use to implement selection sort:\u00a0<\/p>\npublic int[]? NumArray { get; set; }<\/code><\/p>\nSortArray<\/code> method that iterates through the NumArray<\/code> and sorts it in place:<\/p>\npublic int[] SortArray()\r\n{\r\n var arrayLength = NumArray.Length;\r\n\r\n for (int i = 0; i < arrayLength - 1; i++)\r\n {\r\n var smallestVal = i;\r\n\r\n for (int j = i + 1; j < arrayLength; j++)\r\n {\r\n if (NumArray[j] < NumArray[smallestVal])\r\n {\r\n smallestVal = j;\r\n }\r\n }\r\n\r\n var tempVar = NumArray[smallestVal];\r\n NumArray[smallestVal] = NumArray[i];\r\n NumArray[i] = tempVar;\r\n }\r\n return NumArray;\r\n}<\/pre>\ntempVar<\/code>\u00a0and smallestVal<\/code>) that hold values during the sorting process.\u00a0As the outer loop iterates, smallestVal<\/code> holds the current position of the array while the inner loop compares the current minimum value to the rest of the elements.\u00a0<\/p>\narrayLength<\/code> limit. \u00a0<\/p>\nvar array = new int[] { 73, 57, 49, 99, 133, 20, 1 };\r\nvar expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };\r\nvar sortFunction = new Selection();\r\nsortFunction.NumArray = array;\r\n\r\nvar sortedArray = sortFunction.SortArray();\r\n\r\nAssert.IsNotNull(sortedArray);\r\nCollectionAssert.AreEqual(sortedArray, expected);<\/pre>\n<\/a>Time and Space Complexity of Selection Sort<\/h2>\n
<\/a>Advantages of Using Selection Sort<\/h2>\n
<\/a>Disadvantages of Using Selection Sort<\/h2>\n
<\/a>Selection Sort Algorithm Performance in C#<\/h2>\n
public static int[] AddRandomElements(int size)\r\n{\r\n var array = new int[size];\r\n var rand = new Random();\r\n var maxNum = 10000;\r\n\r\n for (int i = 0; i < size; i++)\r\n array[i] = rand.Next(maxNum + 1);\r\n\r\n return array;\r\n}<\/pre>\nAddRandomElements<\/code> method takes the length of the array as its input. Using the inbuilt Random<\/code> class, we generate integer values (less than 10000) that we’re going to put into the array.<\/p>\nAddSortedElements<\/code> that generates a sequence of elements:<\/p>\npublic static int[] AddSortedElements(int size)\r\n{\r\n var array = new int[size];\r\n\r\n for (int i = 0; i < size; i++)\r\n array[i] = i;\r\n\r\n return array;\r\n}<\/pre>\nint[] smallArray = AddRandomElements(200);\r\nint[] mediumArray = AddRandomElements(2000);\r\nint[] largeArray = AddRandomElements(200000);<\/pre>\n
AddRandomElements<\/code>\u00a0method. Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:<\/p>\n| Method | NumArray | Mean | Error | StdDev |\r\n|---------- |-------------- |-----------------:|-----------------:|-----------------:|\r\n| SortArray | Int32[200000] | 50,512,655.47 \u03bcs | 1,002,122.393 \u03bcs | 1,468,898.010 \u03bcs |\r\n| SortArray | Int32[2000] | 3,843.17 \u03bcs | 187.741 \u03bcs | 553.558 \u03bcs |\r\n| SortArray | Int32[200] | 40.56 \u03bcs | 1.775 \u03bcs | 5.232 \u03bcs |<\/pre>\n