sri ramanuja seva

Suppose we are given an array A :

|__20__|__4__|__25__|__10__|__3__|__22__|__16__| 
   [1]   [2]    [3]    [4]   [5]    [6]    [7]

The array has 7 elements as shown above.
Let’s say we want to insert an element into the array. Let’s say we want to insert the value 50 at index (position) 4.
So, in essence, we want the array to be:

 |__20__|__4__|__25__|__50__|__10__|__3__|__22__|__16__| 
    [1]   [2]    [3]    [4]    [5]    [6]   [7]    [8] 

What did we do above?

• Value 50 was inserted at index 4.
• The elements which were originally at indices 4 though 7 were all shifted one position to the right.
  (That is, earlier 10 was at index 4. Now, 10 goes to index 5.
  Similarly, earlier, 3 was at index 5. Now, 3 is at index 6.
  Similarly, earlier 22 was at index 6. Now, 22 is at index 7.
  And again, 16 was at index 7. Now, it goes to index 8. )

Let’s look at another example:
We have array A:

|__20__|__6__|__10__|__12__|__9__|__15__|
   [1]   [2]    [3]    [4]   [5]    [6]

We want to insert the value 2 at index (position) 5.
So, the modified array should look like:

A: |__20__|__6__|__10__|__12__|__2__|__9__|__15__|
      [1]   [2]    [3]   [4]    [5]   [6]    [7] 

(Value 2 has been inserted at position 5, and the elements to the right of it have been shifted right by one position each.)

Our task is to develop a simple algorithm to perform the above task.

Input: (1) Array A[1…n] having n elements, indexed from 1 to n.
(2) value v, which is to be inserted at index k.
(Note: its quite common to have indices go from 0 to n-1. But, for sake of convenience, we are having the indices go from 1 to n. This is also fine.)

In essence, we need to do 2 things:

1. Set the value of A[k] to be v. That is, A[k] <– v.
2. Shift all elements at indices k through n, one position to the right. (That is, as we saw in the examples above, the elements which follow the inserted value are all to be shifted by one position.)
   

Let’s take the 1st example we saw above, and try to do the above 2 steps, and see if it works:

Array A : |__20__|__4__|__25__|__10__|__3__|__22__|__16__| 
             [1]   [2]    [3]    [4]   [5]    [6]    [7]

We want to insert value 50 at index 4.

Let’s follow the steps given above:
Set A[4] to have the value 50. That is, A[4] <– 50.
So, now, A[4] has the value 50, which is what we wanted.

Array A : |__20__|__4__|__25__|__50__|__3__|__22__|__16__| 
             [1]   [2]    [3]    [4]   [5]    [6]    [7] 

But, we encounter a problem here. The value which was earlier at index 4, (that is, the value 10) has been overwritten. That value is lost, it is no longer available to us.
Solution: Before setting A[4] as 50, we should store the original value of A[4] somewhere. Then this problem won’t arise.

We know that 10 should go to A[5] in the modified array. So, why not store the value 10 at A[5] itself. And then we can assign A[4] to be 50, and we won’t have a problem.
Le’ts see:

Original Array A : |__20__|__4__|__25__|__10__|__3__|__22__|__16__| 
                      [1]   [2]    [3]    [4]   [5]    [6]    [7]

Step: Set A[5] to be the value 10.

Modified Array A: 
|__20__|__4__|__25__|__10__|__10__|__22__|__16__| 
   [1]   [2]    [3]    [4]    [5]    [6]    [7]

Now, we are free to set A[4] to be the value 50.

(A: |__20__|__4__|__25__|__50__|__10__|__22__|__16__| 
       [1]   [2]   [3]     [4]    [5]    [6]    [7] )

But again, there’s a problem with this approach. The original value at A[5] (which was the value 3) has been lost. It has been overwritten by 10.
Solution: Before we set A[5] as 10, we need to safely store the value of A[5] somewhere. Then, we can assign the value 10 to A[5].

We know that what was originally at A[5] should go to A[6[ in the modified array.

Original Array A : |__20__|__4__|__25__|__10__|__3__|__22__|__16__| 
                      [1]   [2]    [3]    [4]    [5]   [6]    [7]

So, let’s do that:
A[6] <– 3.
(Then we can set A[5] as 10, and after that, we can set A[4] as 50.)

But, again, on the same lines of the problems we encountered earlier, the original value of A[6] (that is, the value 22) should not get lost.
Solution: we’ll store it in A[7], and then we’ll assign the value 3 to A[6].

So, A[7] <– 22
We’ve set A[7] to have the value 22. (Now, we are free to set A[6] to be 3, and then, A[5] to be 10, and then A[4] to be 50. ]

But, again, as we saw earlier, the original value of A[7] (the value 16) needs to be safely stored before we can assign a new value to A[7].
We know that 16 should be at index 8 in the modified array.
Let’s set A[8] to be 16.
A[8] <– 16.
The originally value of A[7] is safely stored at A[8]. So, we can set a new value at A[7].
A[7] <– 22.
(22 was earlier at A[6]. Now, we’ve put it at A[7]. )
Then, we can set: A[6] <– 3.
(3 was originally at index 5. Now, we’ve put it as A[6].)
Then, we can set A{5] <– 10.
(10 was earlier at A[4]. Now, we’ve set it as the value of A[5].)
And finally, we can put: A[4] <– 50.

So, the modified array looks like:

A: |__20__|__4__|__25__|__50__|__10__|__3__|__22__|__16__| 
      [1]    [2]   [3]    [4]    [5]    [6]   [7]    [8] 

Important: Pls note what we did in order to overcome the problem of the original values of the array getting overwritten. We shifted the elements (one position each to the right) starting from the last element. By that, both our purposes were accomplished: The element got shifted to the right, and the overwriting problem was avoided.
(If we had started shifting the elements (one position each to the right) starting from index k, then the overwriting problem would have been there. Hence, we did the shifting starting from the last element (A[7]) and coming backwards towards A[k].)

Algorithm pseudo-code

Input: (1) Array A[1…n]
(2) Value v to be inserted at index k.

Output: Array A with the value inserted.

Algorithm:

for index i going from n down to k: 
               Set A[i+1] <-- A[i] . 
Set A[k] <-- v. 

Time complexity / Running time analysis

There are at most O(n) iterations of the for-loop (Line 1 of Algorithm). In each iteration, one assignment is done (Line 2 of Algorithm). That is, O(1) time is needed in each iteration. Therefore, time complexity of for-loop is O(n).
In addition, one assignment is done in Line 3, outside of the for-loop. That takes O(1) time.
Therefore, total time complexity is O(n).

Similar posts, on algorithms: How to find minimum value in an array?