Algorithm: Sorting and Insertion Sort

Hey folks,
Hope you all are doing well.

Today, I attended an online lecture about sorting and insertion sort on MIT Open CourseWare.
So here are the things I've learnt from it.

First of all sorting. Why sorting is required ?
Well this question deserves a lot of discussion but due to time and space limit I'll be discussion some important aspects of the sorting with some real world applications.

First, you all know what sorting is, right ? If not sure, please visit this Wikipedia Article for the same.
Now, some of the applications of sorting are: arrangement of phonebook, or arrangement of media files or gallery files based on the specific criteria like based on name, size or date of creation etc.

Now some real world application: To find Median of given list. Median is a value in bunch of numbers where the quantity of the numbers less than the median are equal to the quantity of the numbers greater than the median. I guess this would be complex a little bit, but once you understand the above statement, it will be very easy for you to remember it.

Now the insertion sort.
Insertion Sort:

Here is the basic algorithm for the insertion sort. Its an abstract form of the algorithm,

For i=1,2,3...n
insert A[i] into sorted array A[0, i-1] by pairwise comparison and swaps down to the correct position.

This is the basic or the critical section of the algorithm. Lets understand the working using the below trace.

Step 1:
Given list is 5, 2, 4, 6, 1, 3
Total number of elements n=6

Note: Why didn't we take A[0] as a key.?
Answer: Its obvious not to compare the element with it self. So we will take the first element and compare it with the next one. Hope it is clear to you people.

Step 2:
Now that we have performed the swap, we need to update the base element and the key for the next comparison.

Now again, we will be comparing 5 and 4, and swap if required.

Step 3:
Now the key value and base element will be updated again.

Here the key is actually greater than the base element, so now swap will be performed, the base list will remain unchanged for the next iteration.

Step 4:
Now the key value will be again changed and the base element will be updated.

Note that, after the first swap, the key will remain unchanged until it compares with the remaining elements in the sorted list. Remember the definition here. Placing the A[i] in the sorted array A[0, i-1] in the correct position.

So Key element will be compared with 6, 5, 4, and 2 and swap all the way with all the elements to find the correct position for that element, until it finds out the correct position for itself.

Step 5:
Now again the key will be updated to 3 and base element will be updated to A[4] which is 6 in our case. And again the above method will be applied.

After following 6 steps of the above mentioned method, we will get out sorted list.

Conclusion:

Here you can see that,
Compares >> swaps
It means, the compare operations are way more than the swap operations which makes this algorithm A[n*n] (That is n square actually, but I don't know how to represent it here on the blogger]

One option to solve this is using binary search on the already sorted array A[0, i-1] and place the element at the correct position.

This variation of the algorithm is technically called binary insertion sort which follows given steps:
1. Binary search for the best suitable position for the A[i] element,
2. Swap, similar to the swaps being performed in the insertion sort.

Thats it. Thats all what I got from the lecture. Hope it helps you people in the process of understanding the algorithms.

...... Next Time.... :) :)