1. Insertion Sort

 

Input

A sequence of unordered number ( a1,a2,a3 .... an)

Output

a1 <= a2 <= a3 <= a4 <= .... <= an

We start with insertion sort, which is an efficient algorithm for sorting a small number of elements.

Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left

Insertion Sort Works

Pseudocode

INSERTION-SORT(A)

1 for j = 2 to A.length

2 key = A[j]

3 // Insert A[j] into the sorted sequence A[1 .. j - 1 ].

4 i = j - 1

5 while i > 0 and A[i] > key

6 A[i + 1] = A[i]

7 i = i - 1

8 A[i + 1] =  key

Explanation

iterates the elements from the 2nd position. compare the elements from right to left and swap them. each loop, we will have the subarray [ 1 .. j-1] that will be sorted. remaining [ j+1, ... n ] elements are unsorted elements.so theoretically, A[1 ... j-1 ] for each iteration called loop invariant.

loop invariant per iteration

has three qualities

1. Initialization - before the iteration starts line# 1 in pseudocode, it is always true

2. Maintenance - we can see the changes in each iteration. hence we can compare before iteration changes

3. Termination - on considering initialization and maintenance holds true for each iteration, when the loop terminates, 

   loop invariant will give the final result. here sorted output is the result

The benefit of loop invariant

• loop invariant to show the correctness of the program.
• Typically, we use the loop invariant along with the condition that caused the loop to terminate.

Exercises

Problem 1

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the

array A = { 31,  41,  59, 26, 41, 58 }.

Problem 2

Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing

order.

Problem 3

Consider the searching problem:

Input: A sequence of n numbers A =  { a1, a2, .... an } and a value v

Output: An index i such that v = A [i] or the special value NIL if v does not

appear in A.

Write pseudocode for linear search, which scans through the sequence, looking

for v. Using a loop invariant, prove that your algorithm is correct. Make sure that

your loop invariant fulfills the three necessary properties.

Problem 4

Consider the problem of adding two n-bit binary integers, stored in two n-element

arrays A and B. The sum of the two integers should be stored in binary form in

an (n + 1)- element array C. State the problem formally and write pseudocode for

adding the two integers.

Examples

(venv) [velmuruganponnusamy@localhost insertion-sort]$ python insertionSort.py 

input given:[5, 2, 4, 6, 1, 3]

********************************************************************************

loop invariant before sort [5, 2]

loop invariant after sort [2, 5]

********************************************************************************

loop invariant before sort [2, 5, 4]

loop invariant after sort [2, 4, 5]

********************************************************************************

loop invariant before sort [2, 4, 5, 6]

loop invariant after sort [2, 4, 5, 6]

********************************************************************************

loop invariant before sort [2, 4, 5, 6, 1]

loop invariant after sort [1, 2, 4, 5, 6]

********************************************************************************

loop invariant before sort [1, 2, 4, 5, 6, 3]

loop invariant after sort [1, 2, 3, 4, 5, 6]

********************************************************************************

[1, 2, 3, 4, 5, 6]

(venv) [velmuruganponnusamy@localhost insertion-sort]$ cat insertionSort.py 

def insertionSort(A):

    print("input given:{0}".format(A))

    print("*" * 80)

    length = len(A) #lenght of the Array

    # index of and list start from 0.

    # we start from index 1 and compare the elements from right  to left

    for j in range(1, length):

        key = A[j] # key is to compare and swap

        i = j - 1 # to build loop invariant

        print("\t\tloop invariant before sort {0}".format(A[:j+1]))

        while i >= 0 and A[i] > key: # compare right to left

            A[ i + 1 ] = A[i] # swap the elements

            i = i - 1

        # swap the key for the position 

        # that satisfies A[i] > key

        A[i + 1] = key

        print("\t\tloop invariant after sort {0}".format(A[:j+1]))

        print("*" * 80)

    return A

        

print(insertionSort([5,2,4,6,1,3]))

(venv) [velmuruganponnusamy@localhost insertion-sort]$ python3 insertionSortDesc.py 

input given:[5, 2, 4, 6, 1, 3]

********************************************************************************

loop invariant before sort [5, 2]

loop invariant after sort [5, 2]

********************************************************************************

loop invariant before sort [5, 2, 4]

loop invariant after sort [5, 4, 2]

********************************************************************************

loop invariant before sort [5, 4, 2, 6]

loop invariant after sort [6, 5, 4, 2]

********************************************************************************

loop invariant before sort [6, 5, 4, 2, 1]

loop invariant after sort [6, 5, 4, 2, 1]

********************************************************************************

loop invariant before sort [6, 5, 4, 2, 1, 3]

loop invariant after sort [6, 5, 4, 3, 2, 1]

********************************************************************************

[6, 5, 4, 3, 2, 1]

(venv) [velmuruganponnusamy@localhost insertion-sort]$ cat insertionSortDesc.py 

def insertionSort(A):

    print("input given:{0}".format(A))

    print("*" * 80)

    length = len(A) #lenght of the Array

    # index of and list start from 0.

    # we start from index 1 and compare the elements from right  to left

    for j in range(1, length):

        key = A[j] # key is to compare and swap

        i = j - 1 # to build loop invariant

        print("\t\tloop invariant before sort {0}".format(A[:j+1]))

        while i >= 0 and A[i] < key: # compare right to left

            A[ i + 1 ] = A[i] # swap the elements

            i = i - 1

        # swap the key for the position 

        # that satisfies A[i] > key

        A[i + 1] = key

        print("\t\tloop invariant after sort {0}".format(A[:j+1]))

        print("*" * 80)

    return A

        

print(insertionSort([5,2,4,6,1,3]))