Skip to main content

Algorithm Analysis and Data Structures | Insertion Sort

Theory

In insertion sort we will scan the elements to be sorted with a pointer(say i) from left to right.

Every element on the left of i would have sorted and elements on right have to be sorted.

For every incremental in i pointer, we will use another pointer(say j) to scan form i to its left.

With every step of of j form i to left side of i, compare the jth and (j-1)th element.

If jth element is less than (j-1)th element swap both of them and step down the j for next comparison .

Continue the same till it finds jth element is greater than or equal to (j-1)th element.

If its finds jth element is greater than or equal to (j-1)th element, again increment the i pointer and do the same left traversal with j pointer starting form new i location to its left.

Code


N = 5;
a[] = {1, 6, 4, 3, 6}; //Array with number of elements N =5

for (int i = 0; i < N; i++) //i pointer loop to scan from left to right
{
for (int j = i; j > 0; j--) //j pointer loop to scan from i to its left
{
if( a[j] < a[j-1] ) swap(a, j , j-1); // function to exchange elements if a element is greater than its previous/left one
else break; // to break j pointer loop once the all element of i pointer is get sorted
}
}

In selection sort, the pointer used for find smallest element from unsorted region has to traverse through all the elements for choosing smallest one.

On every rise in steps of pointer which differentiates sorted and unsorted region, there will be a net time complexity about N2/2

But in insertion sort the number of operations for traversal, to insert a element in right position in sorted region will always depends on to up to what extent the given elements had already been sorted.

On an average, half of the elements in sorted region takes part in comparison operation on every incremental steps of pointer which distinguishes between sorted and unsorted regions.

So net time complexity will be about N2/4. Twice as faster than selection sort.

When insertion sort apply on elements which are already sorted, it gives best case output with a simple N number of comparison.

And it performs worst of order ~ N2/2 for reversely sorted set of input.

Comments

Popular posts from this blog

Operating Systems | Scheduling Algorithms : Round Robin

| FCFS | SJF | SRTS | Round Robin | LJF | Priority Scheduling | HRRN | Round RobinFeatures : Most popular algorithm of allPractically implementableImplementable with basic data structures like queueExtremely lesser starvationOptimum efficiency can be set by controlling time quantumThe round robin algorithm will continuously switch between processes if a process in CPU (under execution) exceeds a time limit set by OS called time quantum.Flow Chart :Scheduler allocated process to for execution.CPU starts monitoring the execution time right after from allocation.If the process completes its execution before exceeding time quantum, OS forwards the process to termination state.else, the processes gets preempted once the time quantum limit exceeded and if the process finished at this moment, OS moves the process to termination state, else it moves to ready queue and iterates over the whole process listed above.Example : Consider the following table of processes and calculate complet…

Operating Systems | Concept of Process

Hard disk drive of the system in called primary memory and secondary memory is Random Access Memory(RAM). Either a program written in High Level Language(HLL) or a executable code generated by the sequence of works done by pre-processor, compiler and assembler, resides in secondary memory of the system. To start an execution, operating system allocates some space in the main memory, for the program to be executed and loads the program in the secondary memory to the allocated space. The piece of work which is loaded by the operating system to the main memory in order to execute program is called processEvery program loaded by operating system will create a focus boundary(or process body), a partitioned memory area where all memory requirements for the execution of program is satisfied.Variable which will not change its value through out life time of process is called static variable and variables which are globally accessible in a process known as global variable.Heap area is reserved f…

Operating Systems | Scheduling Algorithms : SJF

| FCFS | SJF | SRTS | Round Robin | LJF | Priority Scheduling | HRRN | Shortest Job First(SJF)SJF algorithm schedules the shortest job(low burst time) available on main memory at the time of context switching in ready state . It can be either preemptive or non-preemptive depending on the nature of scheduler.Since the SJF select the job which is shorted among available jobs on main memory, Non-preemptive SJF algorithm will have larger waiting time if a job with longer burst time get scheduled first. In short SJF is also vulnerable to Convoy EffectTo find shortest process among min-heap would be the best data structure to be usedExample : Consider the following table of processes and calculate completion time, turn around time and waiting time using SJF algorithm with the following assumptions. No preemption.No I/O request will be there from any process.Arrival time is relative to CPU on time.Process NumberATBT103222324442View Answer

The execution of processes can be visualized …