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

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
Participants2253
In this section, we consider an application of the decreasebyone 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.
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 worstcase 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 worstcase 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, almostsorted 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 averagecase 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 twiceasfast averagecase performance coupled with an excellent efficiency on almostsorted arrays makes insertion sort stand out among its principal competitors among elementary sorting algorithms, selection sort and bubble sort.