/***************************************************
* 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.
