Search This Blog

Loading...

Thursday, April 15, 2010

Array and Row Major, Column Major order arrangement of 2 d array

Array in Java

This page is mainly for ISC Students on array address calculation.
An array is a list of a finite number of homogeneous data elements.The number of elements in an array is called the array length. Array length can be obtained from the index set by the formula :
Length=UB-LB+1
Where UB is the largest index , called the upper bound and LB is the smallest index , called the lower bound. Suppose int Arr[10] is an integer array. Upper bound of this array is 9 and lower bound of this array is 0 ,so the length is 9-0+1=10.

In an array ,the elements are stored successive memory cells.Computer does not need to keep track of the address of every elements in memory.It will keep the address of the first location only and that is known as base address of an array. Using the base address , address of any other location of an array can be calculated by the computer.Suppose Arr is an array whose base address is Base(Arr) and w is the number of memory cells required by each elements of the array Arr.The address of Arr[k] – k being the index value can be obtained by using the formula :

Address(Arr[k])=Base(Arr)+w(k-Lower Bound)

2 d Array :- Suppose Arr is a 2 d array.The first dimension of Arr contains the index set 0,1,2, … row-1 ( the lower bound is 0 and the upper bound is row-1) and the second dimension contains the index set 0,1,2,… col-1( with lower bound 0 and upper bound col-1.)

The length of each dimension is to be calculated .The multiplied result of both the lengths will give you the number of elements in the array.

Representation of 2 d array in memory


Let’s assume Arr is an two dimensional 2 X 2 array .The array may be stored in memory one of the following way :-

1. Column by column I,e column major order
2. Row by row , I,e in row major order. The following figure shows both representation of the above array.

By row-major order, we mean that the elements in the array are so arranged that the subscript at the extreme right varies fast than the subscript at it’s left., while in column-major order , the subscipt at the extreme left changes rapidly , then the subscipt at it’s right and so on.

1,1
2,1
1,2
2,2
Column Major Order
1,1
1,2
2,1
2,2
Row major

Now we know that computer keeps track of only the base address. So the address of any specified location of an array , for example Arr[j,k] of a 2 d array Arr[m,n] can be calculated by using the following formula :-
(Column major order ) Address(Arr[j,k])= base(Arr)+w[m(k-1)+(j-1)]
(Row major order) Address(Arr[j,k])=base(Arr)+w[n(j-1)+(k-1)]
For example Arr(25,4) is an array with base value 200.w=4 for this array.The address of Arr(12,3) can be calculated using row-major order as

Address(Arr(12,3) )= 200+4[4(12-1)+(3-1)]
=200+4[4*11+2]
=200+4[44+2]
=200+4[46]
=200+184
=384

Again using column-major order
Address(Arr(12,3) )= 200+4[25(3-1)+(12-1)]
=200+4[25*2+11]
=200+4[50+11]

=200+4[61]
=200+244
=444

13 comments:

  1. really very good explantion .. .

    ReplyDelete
  2. I WANTED TO WRITE SUCH A PROGRAM THAT ACCEPTS ANY NUMBER OF CHARACTER FROM THE USER & DISPLAY THEM IN ASSENDING ORDER. BUT IT IS NOT RUNNINNG PROPERLY IN BLUEJ IN THE ACCEPTANCE TIME. SO PLEASE SEND ME THE ACCTUAL PROGRAM THAT ACCEPTS CHARACTER SINLGY.
    THANKING YOU.
    ASHOK KUMAR PAL
    DURGPUR

    ReplyDelete
  3. This was pretty helpful, not even my book explains it this clearly. Thanks!

    ReplyDelete
  4. thnx fr d easy solution sir.......!!!!!

    ReplyDelete
  5. thnks a lot....helpful for self learners like me

    ReplyDelete
  6. Thank you very much sir..... I am MCA students and confused in address calculation and Row and Column representation of arry.

    The books i have which is very complicated. Your tutorial is so easy so any one can learn it easily.

    Thanks...

    ReplyDelete
  7. Thank you sir very much..awesome explanation

    ReplyDelete

CHECK HERE FOR PREVIOUS POSTS

Google+ Followers

Subscribe via email

Enter your email address:

Delivered by FeedBurner