Selection Sort – Data Structures and Algorithms using C#

Selection sort is among the simplest of sorting techniques and it work very well for small amounts of data. It starts with finding the first smallest element and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire list is sorted.

C# Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Program
{
        static void Main(string[] args)
        {
            int[] arr = { 5, 12, 4, 32, 67, 23, 9, 14, 99, 21};
 
            // call the function InsertionSort
            SelectionSort(arr);
 
            // print the sorted array
            Console.WriteLine("Sorted Array: ");
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + " ");
            }
 
            Console.ReadKey();
        }
 
        public static void SelectionSort(int[] arr)
        {
            //pos_min is short for position of min
            int pos_min, temp;
 
            for (int i = 0; i < arr.Length - 1; i++)
            {
                pos_min = i;//set pos_min to the current index of array
 
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[pos_min])
                    {
                        // pos_min will keep track of the index that min is in, 
                        // this is needed when a swap happens
                        pos_min = j;
                    }
                }
 
                // if pos_min no longer equals i than a smaller value 
                // must have been found, so a swap must occur
                if (pos_min != i)
                {
                    temp = arr[i];
                    arr[i] = arr[pos_min];
                    arr[pos_min] = temp;
                }
            }
        }
}
Complexity of Selection Sort

To find the 1st minimum element from the array of size n, (n – 1) comparisons are required. To find the 2nd minimum element from the unsorted  array of size (n-1), (n – 2) comparisons are required, and so on. Therefore, The number of comparison needed to perform selection sort is:

(n – 1) + (n – 2) + … + 1 = n(n – 1)/2

i.e O(n^2)

Hence, we can say that the bubble sort runs in O(n^2) time in its best, worst and average cases.

Selection sort is a space complexity of O(1).

So, it was all about Selection Sorting Algorithm, if you have any query then please comment below and let us know. If you liked this article, then please follow us on Facebook to get notification for new posts.

Happy Learning 🙂

Rahul is a Data Geek, technology enthusiast, a passionate writer, thinker with passion for computer programming.  He loves to explore technology and finds ultimate joy when writing about trending technology, geek stuff and web development.