In inserted sorted algorithm we compare the current element value with the previous element value. If the current value is smaller than the previous value we swap. This continues until the complete list is sorted.
Let us try to understand the same by using the below diagram. In the below figure you can see we have an unsorted list with values 6,1,3,2.
Step 1 :- So we start with the first element i.e. “6”.There is no element before 6 , so we leave it and we start from 1. We compare “6” and “1”. “1” is smaller than “6”, so we swap.
Step 2:- Now we move to the next element “3”. Is “3” smaller than “6”, yes. So we again swap.
Step 3:- Now we compare “6” with the next element “2”. “2” is smaller so we swap again. There are no more further elements which can be compared with “6”. So the “6” value iteration stops here.
Step 4:- Now we take the next element “1”. There is no element before “1” so we move ahead. We move to the next element “3”. Is “3” smaller than “1” , no , so things are left where they are. So the iteration for “1” is done.We then move to the next element “3”. We compare “3” with “2”. “2” is smaller than “3” so we swap. Now “3” is compared with the next element “6”. “3” is smaller than “6” so the elements are left where they are.
Step 5 :- Now we take the last element “2”. “2” element is larger is than “1”, so “2” and “1” stay where they are. The complete collection is now sorted.
Below is a simple c# inserted algorithm code.
class Program
{
// array of integers which holds unsorted value.
private static int[] UnSortedArray = new int[4]{6,1,3,2};
// Insertion Sort Algorithm
static void Main(string[] args)
{
sortArray();
foreach (int i in UnSortedArray)
{
Console.WriteLine(i);
}
Console.ReadLine();
}
public static void sortArray()
{
int MainLoop; // This variable will helps us loop through all the elements
int InnerLoop; // This variable will help us loop through all elements for every value
int CurrentValue;
for (MainLoop = 1; MainLoop < UnSortedArray.Count(); MainLoop++) // loop through all the elements in the array.
{
CurrentValue = UnSortedArray[MainLoop]; // Take the current value
InnerLoop = MainLoop;
// Loop through all elements for that value
while ((InnerLoop > 0) && (UnSortedArray[InnerLoop - 1] > CurrentValue))
{
//if the previous value is greater than currentvalue swap
UnSortedArray[InnerLoop] = UnSortedArray[InnerLoop - 1];
InnerLoop = InnerLoop – 1;
}
// If previous value is not greater then just keep the value where they are.
UnSortedArray[InnerLoop] = CurrentValue;
}
}
You can also see Algorithm interview questions from www.questpond.com
This question is taken from the book .NET interview question book written by Shivprasad koirala. You can buy the book from these shops à http://dotnetinterviewquestion.wordpress.com/buy-interview-question-books-from-our-shops/
