Array Indices

Publié le 17 août 2015 par Troy

We have all encountered a very awkward situation during our coding session. When we were hastily trying to convert some algorithm to code and bam.. the index problem throws up right in our face. The algorithm uses array index from 1 to n. But the programming language uses from 0 to n-1. What the hell…!!

I have encountered this problem first when I was trying to write insertion sort. Almost all textbooks uses 1 to n index. Why wouldn’t they. Its easier for them that way. With all the analysis and time complexity part coming right next, they wouldn’t have it any other way. But the poor programmer is left with a hell of debugging sessions devoid of all logic and simply trial and error method to find what to subtract/add(/ multiply in odd cases). Although some neat identities like number of numbers from x to y =y-x+1 comes in handy, most of the time, we are simply left counting stars. I’ll illustrate with an Example. Algorithm given for insertion sort in Sahni’s text is following

Algorithm InsertionSort(a,n) //sorts from a[1..n] For j:=2 to n do item:=a[j] i:=j-1 While( i>=1 and item<a[i] )do a[i+1]:=a[i] i:=i-1 end While a[i+1]=item end For end

The conversion of above algorithm into a “normal” C program is following:

void InsertionSort(int *a,int n){ //sorts from a[0..n-1] int item,i,j; for( j=1;j<n;j++){ item=a[j]; i=j-1; while( i>=0 && item<a[i] ){ a[i+1]=a[i]; i=i-1; } a[i+1]=item; } }

Although the actual change is not that big, but when we take a closer look, we can see that none of the array access has been changed. But some test conditions and initialisation have. How are we to know this easily. This, what to change and what not to change dilemma is frustrating and counter productive. If only I could write code like this and be done with it.

void InsertionSort2(int *a,int n){ //sorts from a[1..n] int item,i,j; for( j=2;j<=n;j++){ item=a[j]; i=j-1; while( i>=1 && item<a[i] ){ a[i+1]=a[i]; i=i-1; } a[i+1]=item; } }

How can this possibly work…??

The hack lies in differnt part of the program. Yes the function invokation part. A little trick with pointer arithmetics to set the array pointer to point one address towards the negative side will do a b-e-a-utiful job. You can be hassle free of all the index problems but just remember to call the function as

InsertionSort2(a-1,10)

Now you can convert any algorithm in text books directly to C without having to go through the hustle of thinking about indices.

Another method although not so elegant is to do the pointer subtraction as the first line in the code of subroutine. Readers are encouraged to explore this possibility.

Yes indices. Im done thinking about you. Now my code looks exactly like algorithm. And now I can always say to that friend who never understands my code. Go read the text. I have written exactly that.

NB: On a cautious note, things can go messy when same program has different routines using different index requirements. For example, a subroutine implementing horners rule of polynomial evaluation calls for 0 based indices( It’s easier that way). A good way to avoid confusion is by being consistent about commenting the indices accessed by the function.