Sorting Algorithm

/***************************************************
 * Author : Ajit
 *
 * Description : This file contains implementation of selection sort and insertion sort Algorithm
 *
 /**************************************************/


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace Sorting_Techniques
{
    class Sorting
    {

        /*****************************************************************************/
        /* Method Print
        /*
        /* Description This functions prints the array elements .
        /*
        /* Paremeters  int[] a -array elemets to be printed
                       n - No of elements in Array
        /* Return Void
        /******************************************************************************/

        public static void print(int[] a, int n)
        {
            Console.Write("ARR: ");
            for (int i = 0; i < n; i++)
            {
                Console.Write(a[i]);
                Console.Write(' ');
            }
            Console.Write("\n");
        }

        /*****************************************************************************/
        /* Method Selection Sort
        /*
        /* Description This functions sorts the array elements .
           In a set oF N elements find out the location of the minimum elements and replace it with the location of first element.
           Repeat above step for N-1 elements untill the list is sorted.
        /*
        /* Paremeters  int[] a -array to be sorted
                       n - No of elements in Array
        /* Return Void
        /******************************************************************************/
        public static void selection(int[] a, int n)
        {
            int i;
            int j;
            for (i = 0; i < n - 1; i++)
            {
                for (j = i + 1; j < n; j++)
                {
                    if (a[i] > a[j])
                    {
                        int t = a[i];
                        a[i] = a[j];
                        a[j] = t;
                    };
                }
            }
        }

        /*****************************************************************************/
        /* Method Insertion Sort
        /*
        /* Description This functions sorts the array elements .
           A sublist or Sorted array is maintained which is always sorted .
           N-1 pass are required to sort N elements.
           In each pass , we insert current element at appropriate place so that the elements in current range are in order .s
           Each pass has k comparison where k is the pass no.
        /*
        /* Paremeters  int[] a -array to be sorted
                       n - No of elements in Array
        /* Return Void
        /******************************************************************************/

        public static void insertion(int[] a, int n)
        {
            int i;
            int j;
            int temp;
            for (i = 1; i < n; i++)
            {
                temp = a[i];
                for (j = i - 1; j >= 0 && a[j] > temp; j--)
                {
                    a[j + 1] = a[j];
                }
                a[j + 1] = temp;
            }
        }

        public static int RandomNumber(int min, int max)
        {

            Random random = new Random(DateTime.Now.Ticks.GetHashCode());
            return random.Next(min,max);
        }

        static void Main(string[] args)
        {
            Stopwatch myTimer = new Stopwatch();

            /*  Already Sorted Array*/
            int [] arr_sel_asc =new int [500];
            for (int i = 0; i <= arr_sel_asc.Length-1; i++)
                arr_sel_asc[i] = i;
            int[] arr_ins_asc = new int[500];
            for (int i = 0; i <= arr_ins_asc.Length-1; i++)
                arr_ins_asc[i] = i;

            Console.WriteLine("Array before Sorting");
            print(arr_sel_asc, 500);
            myTimer.Start();
            /* Calling Selection Sort Method for Sorted Array*/
            selection(arr_sel_asc, 500);
            myTimer.Stop();
            Console.WriteLine("Time Taken for Selection Sort for Sorted Array : {0}  ", myTimer.Elapsed);
            Console.WriteLine("Array After Selection Sort");
            print(arr_sel_asc, 500);
            myTimer.Reset();
            myTimer.Start();
            insertion(arr_ins_asc, 500);
            myTimer.Stop();
            Console.WriteLine("Time Taken for Insertion Sort for sorted Array : {0}  ", myTimer.Elapsed);
            Console.WriteLine("Array After Insertion Sort");
            print(arr_ins_asc, 500);

            /* Sorted In Opposite Order */

            int[] arr_sel_desc = new int[500];
            for (int i = arr_sel_desc.Length-1; i >=0; i--)
                arr_sel_desc[i] = arr_sel_desc.Length - 1 - i;
            int[] arr_ins_desc = new int[500];
            for (int i = arr_ins_desc.Length-1; i >=0 ; i--)
                arr_ins_desc[i] = arr_sel_desc.Length - 1 - i;

            Console.WriteLine("Array before Sorting");
            print(arr_sel_desc, 500);
            myTimer.Reset();
            myTimer.Start();
            /* Calling Selection Sort Method for Sorted Array in opposite order*/
            selection(arr_sel_desc, 500);
            myTimer.Stop();
            Console.WriteLine("Time Taken for Selection Sort for Sorted Array in Opposite order : {0}  ", myTimer.Elapsed);
            Console.WriteLine("Array After Selection Sort");
            print(arr_sel_desc, 500);
            myTimer.Reset();
            myTimer.Start();
            insertion(arr_ins_desc, 500);
            myTimer.Stop();
            Console.WriteLine("Time Taken for Insertion Sort for sorted Array in Opposite Order : {0}  ", myTimer.Elapsed);
            Console.WriteLine("Array After Insertion Sort");
            print(arr_ins_desc, 500);


            /* Array element in Random Order*/
            int[] arr_ran = new int[500];
            for (int i = 0; i <= arr_ran.Length-1; i++ )
            {
                arr_ran[i] = RandomNumber(1, 500);
            }

            int[] arr_ran_sel = new int[500];

            for (int i = 0; i <= arr_ran_sel.Length-1; i++)
            {
                arr_ran_sel[i] = arr_ran[i];
            }

            int[] arr_ran_ins = new int[500];

            for (int i = 0; i <= arr_ran_ins.Length - 1; i++)
            {
                arr_ran_ins[i] = arr_ran[i];
            }

            Console.WriteLine("Array before Sorting");
            print(arr_ran_sel, 500);
            myTimer.Reset();
            myTimer.Start();
            /* Calling Selection Sort Method for Sorting array elements in random order*/
            selection(arr_ran_sel, 500);
            myTimer.Stop();
            Console.WriteLine("Time Taken for Selection Sort for Sorting array elements in Random order : {0}  ", myTimer.Elapsed);
            Console.WriteLine("Array After Selection Sort");
            print(arr_ran_sel, 500);
            myTimer.Reset();
            myTimer.Start();
            /* Calling Insertin Sort Method for Sorting array elements in Random order*/
            insertion(arr_ran_ins, 500);
            myTimer.Stop();
            Console.WriteLine("Time Taken for Insertion Sort for sorting array elements in Random Order : {0}  ", myTimer.Elapsed);
            Console.WriteLine("Array After Insertion Sort");
            print(arr_ran_ins, 500);

            Console.ReadKey();
        }
    }
}

Insertion sort perform less comparison than selection sort  depending on the degree of sortedness

of array.Selection sort must scan the remaining parts of the array when placing an element .Insertion sort only scans as many elements as necessary.

When array is already sorted or almost sorted , insertion sort performs in O(n) Time.

Overall insertion sort usually more efficient.

Below image shows time take by insertion sort and selection sort when array is sorted.

Below image Shows time taken by selection sort and insertion sort when arrays is in opposite order(Descending order).

Below image shows time taken by insertion sort and selection sort when arrays element in Random Order. 

Insertion Sort :

The data is sorted by inserting the data into a sorted location.

Insertion sort perform less comparison than selection sort  depending on the degree of sortedness  of array. 

The  time taken by insertion sort would be dependent on the input .Because sorting thousand numbers takes more time thant sorting 3 numbers .More over it is dependent on how the input is sorted .

But the runnig time of program grows with the size of input.

Assumptions:

Costant amount of time is required to execute each line of pseudocode .

for (i = 1; i < n; i++)                   //Execute N times    //Cost C1          

              {

                temp = a[i];                            //Execute N-1 times   //Cost C2

                for (j = i - 1; j >= 0 && a[j] > temp; j--)   //Execute minimum N-1 Times

                                                       //Execute maximum N(N-1)/2 Times

                                                       //Cost C3    

                {

                    a[j + 1] = a[j];                   //Execute maximum N(N-1)/2 Times 

                                                       //Cost C4

                }

                a[j + 1] = temp;                        //Execute N-1 times Cost C5

          }

As per above observation please find below time complexity

Best case complexity : O(n)

Worst Case: O(n^2)

Selection Sort :

The data is sorted by selecting and placing the consecutive elements in sorted location.

Selection sort must scan the remaining parts of the array when placing an element .

            for (i = 0; i < n - 1; i++)           //Execute N times    //Cost C1          

            {

                for (j = i + 1; j < n; j++)    //Execute N(N-1)/2 Times

                                                       //Cost C2    

                {

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

                    {

                        int t = a[i];         //Execute N-1 times //Cost C3

                        a[i] = a[j];          //Execute N-1 times //Cost C3

                        a[j] = t;             //Execute N-1 times //Cost C3

                    };

                }

            }

      

Best Case complexity: O(n^2)

Worst Case Complexity : O(n^2)

Insertion sort is more efficient because you have to search the sorted section where the next element goes where as in selection sort you have to scan the entire unsorted part of the array.