Selection Sort Algorithm using C#

Selection Sort Algorithm is one of the simplest sorting algorithm like BubbleSort. However this is not efficient when it comes to TimeCompexity.

Overview

In this algorithm we try to divide the array into two halves – sorted half and unsorted half. In the first pass, the sorted half contains the first element of the array. In the first pass, we compare the first element (from the sorted half) against the first element in the unsorted half. If first element (in sorted half) is greater than the first element in the unsorted half, we do a swapping of these two items. We continue this process until we finish comparing all elements in the unsorted half. At the end of the first pass, we make sure that first element in the array is the lowest one.This is one pass.

In the second pass, we consider 2nd element in the array and compare against each and every element in the unsorted half. We continue with passing for n-1 iterations (covering up to n-2 th item in the sorted half).

Advantages

  1. Easy to implement the algorithm
  2. In-place sort requires no additional memory for storage

Pseudocode

//Outer loop for passes

for (int i=0 ; i<num.Lenth-1 ; i++)

{

// Inner loop for check and pass

for (int j = i+1; i<num.length;i++)

{

//Check and Swap

if(num[i] > num[j])

{

//Do a swap

temp = a[[i];

a[i] = a[j];

a[j] = temp;

}

}

}

Implementation in C#

using System;

namespace SelectionSort
{
    class Program
    {
        static int [] num = {8,6,5,7,1,2,3};
        static int swapcount = 0;
        static int swapcheck = 0;
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            SelectionSort();
            PrintSortedItems();
        }

        static void SelectionSort()
        {
         
           //Outer loop for number of passes till n-2 th item in the array
            for (int i = 0; i < num.Length-1; i++)
            {
                   int minIndex = i;
                   int passcount = i+1;
                
                Console.WriteLine("This is pass number ----->"+passcount);

                //Inner loop for checking to perform a swap
                for (int j = i+1; j < num.Length; j++)
                {
                    swapcheck = swapcheck+1;
                    Console.WriteLine("  This check for swap -->"+swapcheck);
                    if (num[i]>num[j])
                    {
                        swapcount=swapcount+1;
                        int temp;
                        temp = num[i];
                        num[i] = num[j];
                        num[j] = temp;

                        Console.WriteLine("         This is swap count------->"+swapcount);

                        //minIndex = j;

                    }

                }
                
            }
        }

        static void PrintSortedItems()
        {
            for (int i = 0; i < num.Length; i++)
            {
                Console.WriteLine(num[i]);
            }
        }
    }
}

The complete .NET core project is available in this Github repository https://github.com/sundarnarasiman/SortingAlgorithms

Execution and Results

This is pass number —–>1
This check for swap –>1
This is swap count——->1
This check for swap –>2
This is swap count——->2
This check for swap –>3
This check for swap –>4
This is swap count——->3
This check for swap –>5
This check for swap –>6


This is pass number —–>2

This check for swap –>7
This is swap count——->4
This check for swap –>8
This check for swap –>9
This is swap count——->5
This check for swap –>10
This is swap count——->6
This check for swap –>11


This is pass number —–>3
This check for swap –>12
This is swap count——->7
This check for swap –>13
This is swap count——->8
This check for swap –>14
This is swap count——->9
This check for swap –>15
This is swap count——->10


This is pass number —–>4

This check for swap –>16
This is swap count——->11
This check for swap –>17
This is swap count——->12
This check for swap –>18
This is swap count——->13


This is pass number —–>5
This check for swap –>19
This is swap count——->14
This check for swap –>20
This is swap count——->15


This is pass number —–>6
This check for swap –>21
This is swap count——->16


Printing sorted array
1
2
3
5
6
7
8

Summary

For sorting 7 items, it took 6 passes, 21 checks for swaps and 16 actual swaps. Again, the number of swaps and swap checks are completely dependent on how the elements are arranged in the array. This is not the best performing sorting algorithm. This has the worst case complexity of O(n^2).

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.