Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
In this section, we consider an application of the decrease-by-one technique to sorting an array A[0..n − 1]. Following the technique’s idea, we assume that the smaller problem of sorting the array A[0..n − 2] has already been solved to give us a sorted array of size n − 1: A[0] ≤ … ≤ A[n − 2]. How can we take advantage of this solution to the smaller problem to get a solution to the original problem by taking into account the element A[n − 1]? Obviously, all we need is to find an appropriate position for A[n − 1] among the sorted elements and insert it there. This is usually done by scanning the sorted subarray from right to left until the first element smaller than or equal to A[n − 1] is encountered to insert A[n − 1] right after that element. The resulting algorithm is called straight insertion sort or simply insertion sort.
Though insertion sort is clearly based on a recursive idea, it is more efficient to implement this algorithm bottom up, i.e., iteratively. As shown in Figure 1, starting with A[1] and ending with A[n − 1], A[i]is inserted in its appropriate place among the first i elements of the array that have been already sorted (but, unlike selection sort, are generally not in their final positions).
Here is pseudocode of this algorithm.

preceding elements previously sorted.

part of the array from the remaining elements; the element being inserted
is in bold.
The operation of the algorithm is illustrated in Figure 4.4.
The basic operation of the algorithm is the key comparison A[j ]> v. (Why not j ≥ 0? Because it is almost certainly faster than the former in an actual computer implementation.
The number of key comparisons in this algorithm obviously depends on the
nature of the input. In the worst case, A[j ] > v is executed the largest number of times, i.e., for every j = i − 1,…, 0. Since v = A[i], it happens if and only if A[j ] > A[i] for j = i − 1,…, 0. (Note that we are using the fact that on the ith iteration of insertion sort all the elements preceding A[i] are the first i elements in the input, albeit in the sorted order.) Thus, for the worst-case input, we get A[0]>A[1] (for i = 1), A[1] > A[2] (for i = 2),…,A[n − 2] > A[n − 1] (for i = n − 1). In other words, the worst-case input is an array of strictly decreasing values. The number of key comparisons for such an input is

Thus, in the worst case, insertion sort makes exactly the same number of comparisons as selection sort.
In the best case, the comparison A[j ] > v is executed only once on every
iteration of the outer loop. It happens if and only if A[i − 1] ≤ A[i] for every
i = 1,…,n − 1, i.e., if the input array is already sorted in non decreasing order.
Thus, for sorted arrays, the number of key comparisons is

This very good performance in the best case of sorted arrays is not very useful by itself, because we cannot expect such convenient inputs. However, almost-sorted files do arise in a variety of applications, and insertion sort preserves its excellent performance on such inputs.
A rigorous analysis of the algorithm’s average-case efficiency is based on
investigating the number of element pairs that are out of order It shows that on randomly ordered arrays, insertion sort makes on average half as many comparisons as on decreasing arrays, i.e.,

This twice-as-fast average-case performance coupled with an excellent efficiency on almost-sorted arrays makes insertion sort stand out among its principal competitors among elementary sorting algorithms, selection sort and bubble sort.