Arrays

An array is a collection of variables of the same type that are referenced by a common name. It is a reference data type which stores data values in contiguous memory locations. An array is declared and initialized as follows:

int arr[] = new int[10];

The significance of arrays are as follows:

1. Easy to specify — The declaration, allocation of memory space, initialization can all be done in one line of code.
2. Free from run-time overheads — There is no run-time overhead to allocate/free memory, apart from once at the start and end.
3. Random access of elements — Arrays facilitate random (direct) access to any element via its index or subscript.
4. Fast Sequential Access — It is usually faster to sequentially access elements due to contiguous storage and constant time computation of the address of a component.
5. Simple code — As arrays facilitate access of multiple data items of same type through a common name, the code becomes much simpler and easy to understand.

Each element in an array is referred to by their subscript or index. The index of an element refers to the position of an element in the array. In Java, the indices start from 0 and go on till size - 1.

For example,

int arr[] = {3, 6, 8};

In the array arr[], arr[0] = 3, arr[1] = 6 and arr[2] = 8.

A char data type requires 2 bytes in memory. So, the memory required to store 17 char elements will be 17 X 2 = 34 bytes.

The data type of elements of an array is called base type of an array.

False

Reason — Arrays store same type of data elements in contiguous memory locations and under a single variable name. This makes them very useful where quite many elements of the same data types need to be stored and processed as the user can refer to the elements using the same name and different index numbers.

True

Reason — The index of an element determines its position in an array.

Single-dimensional arrays are lists of information of the same type and their elements are stored in contiguous memory locations in their index order.

For example, an array grade of type char with 8 elements declared as

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 size is 2 bytes and it will be represented in memory as shown in the figure given below:

An int data type requires 4 bytes in memory. Therefore, the storage space required by array A[ ] will be 23 x 4 = 92 bytes.

an index number

Reason — An array element is accessed using the array name along with an index number, which corresponds to the position of the element in an array.

All the elements in an array must be of same data type.

The elements of a seventy-element array are numbered from 0 to 69.

the tenth

Reason — In Java arrays, element at position 1 has index/subscript 0, element at position 2 has index 1, element at position 3 has index 2 and so on. Thus, position of an element is [index + 1]. Hence, amount[9] (9 + 1 = 10) will be the tenth element of the array.

The formula to calculate total number of bytes required by a two-dimensional array is as follows:

total bytes = number-of-rows x number-of-columns x size-of-base-type
                  = 5 x 24 x 2 (since short requires 2 bytes in memory)
                  = 240 bytes

The total number of elements in array B is as follows:

Total elements = number of rows x number of columns
                        = 9 x 15
                        = 135

Two-dimensional arrays are stored in a row-column matrix, where the first index indicates the row and the second indicates the column.

For example, if we declare an array pay as follows:

short[][] pay = new short[5][7];

it will be having 5 x 7 = 35 elements which will be represented in memory as shown below:

The preconditions for Binary Search to be performed on a single dimensional array are:

1. The array should be sorted, either in ascending order or descending order.
2. Lower bound, upper bound and the sort order of the array must be known.

False

Reason — In a case where the search item is at the first place in a sorted array, sequential search becomes faster than binary search as the first comparison yields the desired value. In case of binary search, the search value is found after some passes are finished.

For example, let us consider an array arr[] = {2, 5, 8, 12} and the search value = 2. In this case, sequential search will find the search value in the first comparison while binary search will first compare the search value with the mid value i.e. 5 and continue its passes.

False

Reason — A binary search requires a sorted array. It may be in ascending order or descending order.

True

Reason — Linear search is not affected if an unordered array is sorted in ascending order.

True

Reason — For inserting of an element in a sorted array, the elements are always shifted to make room for the new entrant, the only exception being when the element is inserted at the end of the array.

Some commonly used sorting techniques are:

1. Selection sort
2. Bubble sort
3. Shell sort
4. Shuttle sort
5. Quick sort
6. Heap sort

In the first iteration, the smallest element 1 will be swapped with the element at first index 12. The contents of the array after the first iteration of Selection Sort will be:

$\underset{0}{\boxed{1}}\underset{1}{\boxed{7}}\underset{2}{\boxed{2}}\underset{3}{\boxed{43}}\underset{4}{\boxed{11}}\underset{5}{\boxed{19}}\underset{6}{\boxed{12}}\underset{7}{\boxed{3}}\underset{8}{\boxed{35}}\underset{9}{\boxed{6}}$

In the second iteration, the second smallest element 2 will be swapped with the element at second index 7. The contents of the array after the second iteration of Selection Sort will be:

$\underset{0}{\boxed{1}}\underset{1}{\boxed{2}}\underset{2}{\boxed{7}}\underset{3}{\boxed{43}}\underset{4}{\boxed{11}}\underset{5}{\boxed{19}}\underset{6}{\boxed{12}}\underset{7}{\boxed{3}}\underset{8}{\boxed{35}}\underset{9}{\boxed{6}}$

In the first iteration, (35,6) will be compared and swapped. The array after the first iteration will look like:

$\underset{0}{\boxed{6}}\underset{1}{\boxed{35}}\underset{2}{\boxed{8}}\underset{3}{\boxed{11}}\underset{4}{\boxed{15}}\underset{5}{\boxed{9}}\underset{6}{\boxed{7}}\underset{7}{\boxed{22}}\underset{8}{\boxed{41}}\underset{9}{\boxed{65}}$

In the second iteration, (35,8) will be compared and swapped. After the second iteration, the array will look like:

$\underset{0}{\boxed{6}}\underset{1}{\boxed{8}}\underset{2}{\boxed{35}}\underset{3}{\boxed{11}}\underset{4}{\boxed{15}}\underset{5}{\boxed{9}}\underset{6}{\boxed{7}}\underset{7}{\boxed{22}}\underset{8}{\boxed{41}}\underset{9}{\boxed{65}}$

Selection sort algorithm

Reason — We can see that after three iterations the first three elements of the array are in their correct positions. This happens in Selection sort. In Bubble sort, the heaviest element settles at its appropriate position in the bottom i.e., the array is sorted from the end to the start.

Details of each iteration are captured below:

Array after the first iteration:

$\underset{0}{\boxed{1}}\underset{1}{\boxed{23}}\underset{2}{\boxed{3}}\underset{3}{\boxed{18}}\underset{4}{\boxed{24}}\underset{5}{\boxed{27}}\underset{6}{\boxed{12}}\underset{7}{\boxed{60}}\underset{8}{\boxed{47}}\underset{9}{\boxed{5}}$

Array after the second iteration:

$\underset{0}{\boxed{1}}\underset{1}{\boxed{3}}\underset{2}{\boxed{23}}\underset{3}{\boxed{18}}\underset{4}{\boxed{24}}\underset{5}{\boxed{27}}\underset{6}{\boxed{12}}\underset{7}{\boxed{60}}\underset{8}{\boxed{47}}\underset{9}{\boxed{5}}$

Array after the third iteration:

$\underset{0}{\boxed{1}}\underset{1}{\boxed{3}}\underset{2}{\boxed{5}}\underset{3}{\boxed{18}}\underset{4}{\boxed{24}}\underset{5}{\boxed{27}}\underset{6}{\boxed{12}}\underset{7}{\boxed{60}}\underset{8}{\boxed{47}}\underset{9}{\boxed{23}}$

Bubble sort algorithm

Reason — In bubble sort, the adjoining values are compared and exchanged if they are not in proper order. This process is repeated until the entire array is sorted.

In the first pass, (13,19) will be compared but not swapped. The array after the first pass will be:

$\underset{0}{\boxed{13}}\underset{1}{\boxed{19}}\underset{2}{\boxed{6}}\underset{3}{\boxed{2}}\underset{4}{\boxed{35}}\underset{5}{\boxed{28}}\underset{6}{\boxed{51}}\underset{7}{\boxed{16}}\underset{8}{\boxed{65}}\underset{9}{\boxed{4}}$

In the second pass, (19, 6) will be compared and swapped. The array after the second pass will be:

$\underset{0}{\boxed{13}}\underset{1}{\boxed{6}}\underset{2}{\boxed{19}}\underset{3}{\boxed{2}}\underset{4}{\boxed{35}}\underset{5}{\boxed{28}}\underset{6}{\boxed{51}}\underset{7}{\boxed{16}}\underset{8}{\boxed{65}}\underset{9}{\boxed{4}}$

In the third pass, (19, 2) will be compared and swapped. The array after the third pass will be:

$\underset{0}{\boxed{13}}\underset{1}{\boxed{6}}\underset{2}{\boxed{2}}\underset{3}{\boxed{19}}\underset{4}{\boxed{35}}\underset{5}{\boxed{28}}\underset{6}{\boxed{51}}\underset{7}{\boxed{16}}\underset{8}{\boxed{65}}\underset{9}{\boxed{4}}$

An array is a collection of variables of the same type that are referenced by a common name. It is a reference data type which stores data values in contiguous memory locations. An array is declared and initialized as follows:

int arr[] = new int[10];

The use of arrays have the following benefits:

1. Easy to specify — The declaration, allocation of memory space, initialization can all be done in one line of code.
2. Free from run-time overheads — There is no run-time overhead to allocate/free memory, apart from once at the start and end.
3. Random access of elements — Arrays facilitate random (direct) access to any element via its index or subscript.
4. Fast Sequential Access — It is usually faster to sequentially access elements due to contiguous storage and constant time computation of the address of a component.
5. Simple code — As arrays facilitate access of multiple data items of same type through a common name, the code becomes much simpler and easy to understand.

Arrays are of different types :

1. One-dimensional array — It comprises of finite homogeneous elements.
2. Multi-dimensional arrays — It comprises of elements, each of which is itself an array. A two-dimensional array is the simplest of multidimensional arrays, having two indices (rows and columns).

Single-dimensional arrays are lists of information of the same type and their elements are stored in contiguous memory locations in their index order.

Internally, arrays are stored as a special object containing :

1. A group of contiguous memory locations that all have the same name and same datatype.
2. A reference that stores the beginning address of the array elements.
3. A separate instance variable containing the number of elements in the array.

For example, an array grade of type char with 8 elements declared as

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 size is 2 bytes and it will be represented in memory as shown in the figure given below:

The amount of storage depends upon the type and size of an array as every data type requires different storage space in memory and the number of elements (size) of an array determines how many memory blocks of same size are required.

To calculate the amount of storage required by an array we use the formula:
Size = size of data type x number of elements in an array

For example, int arr[] = new int[10]; will require 4 x 10 = 40 bytes space in memory.

A two-dimensional array is an array in which each element is itself an array. For instance, an array A[M][N] is an M by N table with M rows and N columns containing M x N elements.

The general form of a two-dimensional array declaration in Java is as follows:
type array-name[ ][ ] = new type[rows][columns];

Some situations that can be easily represented by two-dimensional arrays are as follows:

1. In a school, marks obtained by a student in various subjects can be stored in a two-dimensional array, where rows can be used for successive tests (mid term, quarterly, half yearly etc.) and columns can be used for subjects (maths, english, science, hindi, computer etc.).
2. In a business, the sales for a month can easily be represented using a two-dimensional array, where rows can represent weeks and columns can represent the individual days in a week.

Two-dimensional arrays are stored in a row-column matrix, where the first index indicates the row and the second indicates the column.

For example, if we have declared an array pay as follows:
short[][] pay = new short[5][7];

it will be having 5 x 7 = 35 elements which will be represented in memory as shown below :

The amount of storage required to hold a two-dimensional array is also dependent upon its base type, number of rows and number of columns. The formula to calculate total number of bytes required by a two-dimensional array is given below :

total bytes = number-of-rows x number-of-columns x size-of-base-type

Here, the array pay[][] will require 5 x 7 x 2 = 70 bytes of memory space, as the size of a byte type element is 2 bytes.

(i) Linear Search — Linear Search refers to the searching technique in which each element of an array is compared with the search item, one by one, until the search-item is found or all elements have been compared.

For example, consider an array

int arr[] = {5, 8, 11, 2, 9};

and the search item 2. Linear search will compare each element of the array to 2 sequentially until either the search value 2 is found or all the elements have been compared.

(ii) Binary search — Binary Search is a search-technique that works for sorted arrays. Here search-item is com­pared with the middle element of array. If the search-item matches with the element, search finishes. If search-item is less than middle (in ascending array), we perform binary-search in the first half of the array, other­ wise we perform binary search in the second half of the array.

For example, consider an array

int arr[] = {2, 5, 8, 11, 14};

and the search item 11. First, the search value will be compared with the middle value 8. Since the values are not equal, binary search will be performed in the latter half of the array, i.e., {11, 14}. The search value will be compared with the mid value, which will be 11. Since search value is found, binary search will stop.

Binary search is more efficient than linear search as it searches the given item in minimum possible comparisons.

import java.util.Scanner;

public class KboatLinearSearch
{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
    
        int X[] = new int[10];
        int i = 0;
        
        System.out.println("Enter array elements : ");
        for(i = 0; i < 10; i++)  
        {   
            X[i] = in.nextInt();      
        } 

        System.out.println("Input Array is:");
        for (i = 0; i < 10; i++) {
            System.out.print(X[i] + " ");
        }
        System.out.println();
        
        System.out.print("Enter ITEM to search : ");
        int item = in.nextInt();
        
        for (i = 0; i < 10; i++) {
            if (X[i] == item) {
                break;
            }
        }
        
        if (i == 10) {
            System.out.println("Search Unsuccessful");
        }
        else {
            System.out.println("Search Successful");
            System.out.println(item + " is present at index " + i);
        }
        
    }
}

Output

The contents of the array at the end of each iteration are as follows:

Itr 1 — 26, 21, 20, 23, 29, 17
Itr 2 — 21, 26, 20, 23, 29, 17
Itr 3 — 21, 20, 26, 23, 29, 17
Itr 4 — 21, 20, 23, 26, 29, 17
Itr 5 — 21, 20, 23, 26, 29, 17
Itr 6 — 21, 20, 23, 26, 17, 29
Itr 7 — 20, 21, 23, 26, 17, 29
Itr 8 — 20, 21, 23, 26, 17, 29
Itr 9 — 20, 21, 23, 26, 17, 29
Itr 10 — 20, 21, 23, 17, 26, 29
Itr 11 — 20, 21, 23, 17, 26, 29
Itr 12 — 20, 21, 23, 17, 26, 29
Itr 13 — 20, 21, 17, 23, 26, 29
Itr 14 — 20, 21, 17, 23, 26, 29
Itr 15 — 20, 17, 21, 23, 26, 29
Itr 16 — 17, 20, 21, 23, 26, 29

0 to N-1

Reason — In Java, for an array having N elements, the subscripts start from 0 and go on till N - 1 (size - 1).

50 bytes

Reason — The size of char data type is 2 bytes. Since A is an array of char type, the size of each element of the array will be 2 bytes. The size of 25 elements will be 25 X 2 = 50 bytes.

200 bytes

Reason — The size of int data type is 4 bytes. Since B is an array of int type, the size of each element of the array will be 4 bytes. The array has 10 rows and 5 columns, thus total number of elements will be 10 X 5 = 50. The size of 50 elements will be 50 X 4 = 200 bytes.

30

Reason — The total number of elements in array C will be 5 x 3 x 2 = 30.

float average[ ];
double[ ] marks;

Reason — The statements float average[ ]; and double[ ] marks; are valid as they follow the syntax for declaration of an array.

int number( ); uses small brackets () instead of square brackets []. The correct statement will be int number[];.

counter int[ ]; has exchanged the place of data type and array variable. The correct statement will be int counter[];

number[5] is undefined

Reason — The valid subscripts of an array of size N are from 0 to N - 1. Thus, subscripts of array number will be from 0 to 4 (5 - 1).

int x[ ] = int[10];
x = y = new int[10];
int i = new int(10);

Reason — int x[] = int[10]; doesn't contain the 'new' keyword used to initialize an array. The correct statement will be int x[] = new int[10];

In the statement x = y = new int[10];, 'x' and 'y' are not declared as array variables. The correct statement will be :

int x[] = new int[10]; 
int y[] = new int[10];

In the statement int i = new int(10);, 'i' is not declared as array variable and small brackets () are used instead of square brackets []. The correct statement will be int i[] = new int[10];

The remaining statements follow the syntax used for declaring and initializing an array, thus they do not have any error.

76

Reason — The valid subscripts of an array are from 0 to size - 1. Thus, A[0] = 35, A[1] = 26, A[2] = 19, A[3] = 76 and A[4] = 58.

8 and 5

Reason — Two-dimensional arrays are stored in a row-column matrix, where the first index indicates the row and the second indicates the column.

The element stored at z[1][0] refers to the element stored in second row and first column, which is 8.

The element stored at z[0][2] refers to the element stored in first row and third column, which is 5.

3, 5, 8, 12

Reason — Selection Sort is a sorting technique where next smallest (or next largest) element is found in the array and moved to its correct position in each pass.

In the first pass, smallest element 3 will be found and swapped with the first position element 12. The array elements after the first pass will be:

3, 12, 8, 5

In the second pass, the next smallest element 5 will be found and swapped with the second position element 12.The array elements after the second pass will be:

3, 5, 8, 12

3, 8, 12, 5

Reason — The basic idea of bubble sort is to move the largest element to the highest index position in the array. To attain this, two adjacent elements are compared repeatedly and exchanged if they are not in correct order.

In the first pass, adjacent elements (12,3) will be compared and swapped. The array will look like this after the first pass:

3, 12, 8, 5

In the second pass, adjacent elements (12,8) will be compared and swapped. The array will look like this after the second pass:

3, 8, 12, 5

Bubble sort is applied on the array.

Explanation

In the first pass, adjacent elements (18, 13) will be compared and swapped. The array will look like this after the first pass:

13, 18, 2, 9, 5

In the second pass, adjacent elements (18, 2) will be compared and swapped. The array will look like this after the first pass:

13, 2, 18, 9, 5

In the third pass, adjacent elements (18, 9) will be compared and swapped. The array will look like this after the third pass:

13, 2, 9, 18, 5