Site hosted by Angelfire.com: Build your free website today!

Arrays

Definition

An array is a collection of variables of the same type that are referenced by a common name.

Arrays consist of contiguous memory locations. The lowest address corresponds to the first element and the highest address to the last element. Arrays are a way to group a number of items into a larger unit. Arrays can have data items of simple types like int or float, or even of user-defined types like structures and objects.

Types of Arrays

Arrays are of different types:

(i) one-dimensional arrays (single dimensional arrays)

(ii) multi-dimensional arrays

Single dimensional Arrays

The simplest form of an array is a single dimensional array. The array is given a name and its elements are referred to by their subscripts or indices. Java array’s index numbering starts with 0.

Like other variables in Java, an array must be defines before it can be used to store information. Like other definitions, an array definition specifies a variable type and a name along with one more feature size to specify how many data items the array will contain. The general form of an array declaration is:

type array-name[] = new type [size];

or type[] arrayname = new type [size];

Where type declares the base type of the array, which is the type of each element in the array. The array-name specifies the name with which the array will be referenced and size defines how many elements the array will hold. The size must be an integer value or integer constant without any sign.

Definition

The data type of array elements is known as the base type of the array

Declaring Arrays

To declare an array marks of base type int and which can hold 50 elements:

Syntax:

int marks [] = new int [50];

or int [] marks = new int [50];

The above statements declare array marks which have 50 elements, marks[0] to marks[49].

An array must be declared or created before it can be used. This is a two-step process:

R First, declare a reference to an array

R Then, create the array with the new operator.

For instance,

double x[];

x = new double[5];

This can also be written as double x[] = new double[5];

Using Arrays

An array element may be used in any place where an ordinary variable of the same type may be used. An array element is addressed using the array name followed by a integer subscript in brackets eg., a[2], marks[1].

Memory Representation of Single Dimension Arrays

Single-dimension arrays are essentially lists of information of the same type and their elements are stored in contiguous memory location in their index order. For instance an array grade or type char with 8 elements declared as

char grade [] = new char [8];

or char[] grade = new char [8];

will have the element grade [0] at the first allocated memory location, grade [1] at the next contiguous memory location, grade [2] at the next, and so forth. Since grade is a char type array, each element is 2 bytes (A character size is 2 bytes in Java) and it will be represented in memory as shown below: (It is an eight-element character array beginning at location 2000)

Grade

grade[0]	grade[1]	grade[2]					grade[7]

2000	2002	2004	2006	2008	2010	2012	2014

Address

Initializing Arrays

When an array object is created with the new operator, its elements are automatically initialized to zero, which is the default initial value for all numeric types. If the array is Boolean types then all elements are initialized with Boolean false value. Similarly, all elements of character array also get initialized with their default initial value.

Arrays can also be initialized to non-zero values using array initializers, but array initializers only work in declaration statements.

int a[] = {1, 2, 3, 4, 5}; // Create and initialize array

Out of bound subscripts

Each element of an array is addressed using the name of the array and the subscripts 0,1,.., n-1, where n is the number of elements in the array. A subscript which is less than 0 or greater than n-1 is an out of bound subscripts

For example,

In an array Z[6], Z[-5] or Z[7] is an out of bound subscript.

Searching in One dimension Arrays

There are two types of Search 1) linear Search 2) Binary Search

1. Linear Search: - In Linear search each element of the array is compared with the given Item to be search for one by one . This method which traverses the array sequentially to locate the given item is called linear search or sequential search.

Example:

// write a program to search an element in an array using linear search. Pass the element to be searched for as an argument.

class linear

{

public void Lsearch(int n)

{

int A[] = {5,2,8,4,9,1,12,90,15,7};

int flag = 0;

int i;

for(i=0;i<10;i++)

{

if(n == A[i])

{

flag = 1;

break;

}

if (flag == 1)

System.out.println("Element present at position" + (i+1));

else

System.out.println("Element not present");

}

2. Binary Search : This search technique searches the given item in minimum possible comparison. The binary search requires the array to be scanned, must be sorted , must be sorted in any order (either descending or ascending ). In binary search the item is searched for in smaller segment after every stage .

Example:

Write the steps to search ‘44’ and ‘36’ using binary search in the following array data :

10	12	14	21	23	28	31	37	42	44	49	53
1	2	3	4	5	6	7	8	9	10	11	12

Step 1

Beg = 1 Last =12

mid = int(1+12)/2 = int (6.5) = 6

Step 2

Data[mid] i.e. Data[6] is 28

28<44 then

beg = mid +1

beg = 6+1 = 7

Step 3

mid = int(beg + last)/2 = int(7 +12)/2 =9

Data[9] = 42 <44 then

Beg = mid +1

Beg = 9 +1 = 10

Step 4

mid = int (10 +12)/2 = 11

Data[11] i.e. 49> 44 then

Last = mid –1 = 10

Step 5

mid = int(beg +last)/2 = (10 +10) /2 = 10

Data[10] i.e 44 = 44

Search successful at location number 10

// search an element in an arrays whereas linear search can work for both sorted ass we

class Binary

{

public void Bsearch (int n)

{

int A[] = {5,10,15,20,25,30,35,40,45,50};

int flag=0, beg, last, Mid=0;

int big =0;

last =9;

while(big <= last)

{

Mid = (big + last)/2;

if (n> A[Mid])

big = Mid + 1;

else

big = Mid - 1;

{

flag =1;

break;

}

if(flag ==1)

System.out.println("element present at position: " +(Mid +1));

else

System.out.println("element not present" );

}

// Selection sort (program contains error)

class selection

{

public void work(int A[])

{

int i,j, small ,tmp, pos;

for(i =0; i<10; i++)

{

small = A[i];

pos = i;

for(j =i+1; j<9; j++)

{

if(A[i] <small)

{

small = A[j];

pos = j;

}

tmp = A[i];

A[i] = A[pos];

A[pos] = tmp;

}

System.out.println("Array in ascending order is " );

for (i =0; i<10; i++)

System.out.println(A[i] +"\t");

}

//bubble sort (program has error)

class bubble_sort

{

public void bubbel(int A[])

{

int i,j,tmp;

for(i =0; i<10; i++)

{

for(j =0; j<9-i; j++)

{

if(A[j] > A[j+1])

{

tmp = A[j];

A[j] = A[j+1];

A[j+1] = tmp;

}

System.out.println("Array in ascending order is " );

for (i =0; i<10; i++)

System.out.println(A[i] +"\t");

}

Algorithms:

Algorithm for linear Search

Step 1 ctr =0

// intialize counter

Step 2 while (ctr <= n) repeat steps 3 and 4

Step 3 if A[ctr] == search_item then

{

print << search_item << “has been found””<<;

printt<< ctr +1 << “ << “is its position “

exit() // go out of loop to step 6

}

Step 4 ctr = ctr +1

Step 5 Print<< Search_item <<”Not found” <<

Step 6 end

Algorithm for Binary Search

Step 1 Array elements are sorted into ascending order.

Step 2 first = 0 ; Last = N –1; mid =0; find =0

Step 3 While (first < = last) and (opt =0) repeat 4,5 and 6

Step 4 mid = Int (first + last) /2

Step 5 if (A[mid] = search_item) then pos = mid; opt = 1

Step 7 if (opt = 1) then output postion pos

else output “Not found”

Step 8 End

Algorithm for selection sort

Step 1. Intialise a variable small with the first array element small = A[0]

Step 2. Determine the smallest element and its position (posn)

For k = 0 to N-1

Small = A[k]

For J = k to n-1

{

if(A[j] <small )

{

small = A[J];

posn = J ;

}

j = j+1

Step 3. kth element and smallest element are swapped:

{

Temp = A[k]

A[k] =small

A[posn] = temp

// end of the do loop

}

Algorithm for Bubble sort

Steps

1. enter the value of N and the array elements

2. Initialize temp = 0

3. declare integers I and j;

4. construct loop within a loop:

for I = 0 to N – 1;

{

for j = 0 to N – 2;

{

if (A [J] > A[J + 1])

swap A[J] and A [J + 1] by

using the temp as follows :

{ temp = A[J];

A [J] = A [J + 1];

A [J + 1] = temp ;

} // End of the inner loop

} // End of inner loop

} // End of outer loop.

Advantages and disadvantages of arrays

Arrays including Java arrays are static data structures since the number of elements they can store is fixed at the time of creation. The advantages and disadvantages of arrays are being listed below:

Advantages

i. Easy to specify: the declaration, allocation of memory space, initialization can all be done in one line of code.

ii. Free from run-time overheads. There are no run-time overheads to allocate/free memory, apart from once at the start and end.

iii. Random access of elements. Arrays facilitate random (direct) access to any element via its index or subscript ex: Direct access to a student record via student number (index can be derived from student number)

Example:

Byte stuRollNo = 5;

System.out.println(“Marks of roll number” +stuRollNo+ “are” + marks[stuRollno]);

iv. Fast sequential access. It’s usually faster to sequentially access elements due to contiguous storage and constant time computation of the address of a component

Disadvantages

i. Need to know the size. A potential disadvantage of arrays (depending on the application) is the need to know the size at the time of allocation

ii. Careful design required. Careful design is required to make sure that the array will be large enough to hold the largest possible group of data but no longer.