Inserting into arrays – part 4

In the article First look at arrays we saw one more way of inserting our stuff into the locker which was nice and easy.
Quote(from the earlier article):
"In another way of going about it, you would probably start at the locker before the empty one (locker n-1) and transfer all the items in that into the empty one. Then you would move to the previous locker (locker n-2) and move the items in that into the currently empty one (locker n-1). You will keep doing this (quickly – before anybody comes in) until the locker you are interested in is empty. Then you can put your things in – mission accomplished and most probably no one will notice that their stuff has been shifted by one locker! The second approach required only one hand and had the added benefit of being able to look nonchalant and guilt free if anyone walked in while you were half way through the exercise!"

Let us look at the code for that:
Already we have the findEmptyLocker function written. We shall write that function again (with a minor change) so that we don’t have to scroll all the way down to the first article to see it.

public int findEmptyLocker(int insertPos)
    {
    for (int i=insertPos; i < 10; i++)
    {
         if (arr[i].content.equalsIgnoreCase("empty"))
              return i;
     }
    return -1;
}

Now we can write the new function which we will call insertIntelligently. It looks like

public void insertIntelligently(int insertPos, String myStuff)
{
    int pos = findEmptyLocker(insertPos);
    if (pos != -1)
    {
         for (int i = pos; i > insertPos; i--)
              arr[i].content = arr[i-1].content;
         arr[insertPos].content = myStuff;
    }
}

First we find the first empty locker at or to the right of the locker we are interested in.
Once we find it, we move the contents of the locker just before the empty one into the empty one. What we have effectively done is moved the empty locker closer by one slot to where we want it to be! This is the magic I was talking about. We keep doing this until the empty locker is where we want it to be. Having done that, we come out of the for loop and then insert our stuff into the empty locker. Done.
The logic is elegant. We have not used any temporary storage/variables. The code is efficient. What more can we ask for?

The articles on arrays that we have seen so far illustrate a few basic concepts. One is that there are many ways of doing the same thing. Some ways will be better than others, so we should think of at least a few different ways of achieving our goals before comparing them and arriving at the best way forward.
Second, if we can find a real-life analogy to our algorithm, we are able to better grasp the logic behind it.
One caveat: The way we do things physically/mentally need not necessarily be the best way for the computer. Gradually we will have to learn to think in more abstract terms so that we can exploit the inherent strengths of the computer.