Back to Course


0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 22 of 43
In Progress

Insertion Sort

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.

KodNest Capture46
Figure 1: Iteration of insertion sort: A[i] is inserted in its proper position among the
preceding elements previously sorted.
KodNest Capture47
Figure 2: Example of sorting with insertion sort. A vertical bar separates the 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

KodNest Capture48

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

KodNest Capture49

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.,

KodNest Capture50

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.

New Report