Java Chap10 Arrays & Their Applications ( Prof. Ananda M Ghosh.)

Chapter 10: Arrays and Their Applications 10.0 Introduction An array is a collection of finite numbers of data variables (having similar data types only) that can be referred to by a common name. An array of any definite data type [ int, double, String, etc] can be created and used in a program. An array may be of one dimensional, two or many dimensional. A specific element in an array can be accessed by its index. One-dimensional array can be regarded as a linear list of same type data variables, which can be declared as -data-type variable-name[ n ]; where n stands for the size of the array. For example, String month[12]; ..... (a) is declared as an array of months of String type which can accommodate 12 names only. This declaration is not sufficient. Along with such declaration, allocation for physical memory space is also got be ensured. For that, we have to make use of new operator as shown below: month = new String[12]; ......(b) --- since there are 12 months in a year, the size is set to 12 to store the names of respective months. We see that there are two steps involved in creating an array – i) to declare an array variable with size and ii) to allocate memory to hold that array using new operator. Above mentioned two steps can be combined together as... String month[ ] = new String[12]; Once an array is created, any particular element of it can be referred by specifying the index of that element. Array index counts starts with zero. For example, different elements of the array month[12] can be initialized in a way shown below. month[0] = “January”; month[1] = “February”; | | month[10] = “November”;

month[11] = “December”; In example -10.1, you can see a complete program using array declaration, storage allocation and initialization of array elements one after another. Example 10.1 Demo of a Single Dimensional Array public class SingleDimArray { public static void main() { String month[]; month = new String[12]; month[0] = "January"; month[1] = " February"; month[2] = " March"; month[3] = "April"; month[4] = "May"; month[5] = "June"; month[6] = "July"; month[7] = "August"; month[8] = "September"; month[9] = " October"; month[10] = " November"; month[11] = "December"; System.out.println ("In 1947, India wins freedom in the month of " + month[7]+"."); } } If you compile and execute this program, the output will appear as shown below: -In 1947, India wins freedom in the month of August. However, the three steps of array’s declaration, allocation and initialization can be merged together as a single statement as shown in example 10.2. Example 10.2 An Improved way of Array manipulation public class ImprovedSDA { public static void main(){ String month[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};

System.out.println ("In 1947, India wins freedom in the month of " + month[7]+"."); } } The same output will be observed if you run this new program version. Important Points to Note An array always deals with a fixed sized (as declared) collection of data elements. Data elements must be of the similar data types. Element count starts from 0. Array elements are placed in contiguous (with no gap in between) memory locations. 5) If each element takes 4 bytes, then an array of size 20 will occupy a memory space of 80 bytes only. 6) An array can be regarded as a static (fixed size) data structure. 1) 2) 3) 4)

10.0.1 Two Dimensional Array You can declare a (4rows by 12 columns) two dimensional array, named sales, in the following way – double sales[][] = new double [4][12]; where sales[ ][ ] two dimensional array can store sales-figures of 4 salesmen covering 12 months of a year. The sales figures of the first person (month wise) will be stored in sequential elements as sales [0][0] for January, ......., sales[0][11] for December; ........; and gradually in this way, the figures for the fourth person will be stored as sales[3][0], ......., sales[3][11]. Once sales figures are stored in such an array structure, calculations of grand-total, individual total, average marketing capacity, differences from the sales target, etc can be found out very easily. Now we will examine how arrays can make computational work much easier and simpler. 10.1 Different Uses of Arrays Averaging – for estimation of the average of a group of data values, which can be stored as elements of an array and each element can be called and used simply by specifying the array name and the respective index number. Comparing, insert/modify values of any element at random can be done for data processing if relevant data remain stored in the form of an array.

Determination of Max/Min value from any array elements is quite simple. Thus structuring results data in the form of an array can help preparing Merit List of any examination very easily. Random Access – Any element of an array, whether the first, middle or the last element, can be accessed with the same ease and speed. This is a very useful programming feature. A few examples now can show how easily you can make use of an array to manipulate a group of data elements for extracting useful information. Example 10.3 To find Average, and Max/Min values of an array public class AverageDemo { public static void main() { int nostudents = 10; int marks[] = {45,53,98,76,65,71,55,43,87,66}; int sum = 0; for(int i=0; i<10; i++) { sum = sum + marks[i]; } int avmarks = sum / nostudents; System.out.println ("Average mark = " + avmarks); int max = marks[0]; for (int j=1; j<=9; j++) { if ( max < marks[j]) max = marks[j]; } System.out.println (" Maximum Marks = " + max); int min = marks[0]; for (int j =1; j<=9; j++) { if (min > marks[j]) min = marks[j]; } System.out.println (" Minimum Marks = " + min); } }

By running this program, you will see the output as ---

Average mark = 65 Maximum Marks = 98 Minimum Marks = 43 Example 10.4 Use of Two Dimensional Array /* Monthly sales figures for four persons are stored in a two dimensional array and quarterly total for each person is stored in another single dimensional array */ public class SalesDemo { public static void main() { double grandtotal = 0.0; double indvtotal[] = {0.0,0.0,0.0,0.0}; // quarterly sales figures for 4 salesman double sales[][] = new double[4][3]; sales[0][0] = 3451.50; sales[0][1] = 5100.00; sales[0][2] = 3687.50; sales[1][0] = 6710.00; sales[1][1] = 4329.50; sales[1][2] = 3988.00; sales[2][0] = 4433.00; sales[2][1] = 3876.50; sales[2][2] = 3981.50; sales[3][0] = 3987.00; sales[3][1] = 4533.00; sales[3][2] = 4387.00; for (int i=0; i<4; i++){

//outer for loop

for (int j=0; j<3; j++){ // inner for loop indvtotal[i] = indvtotal[i] + sales[i][j]; } System.out.println (i +") Individual Sales figure = "+indvtotal[i]); grandtotal = grandtotal + indvtotal[i]; } System.out.println (" Grand total of Sales = " + grandtotal);

float avsales = (float) grandtotal/4; System.out.println (" Average sales per person = "+ avsales); } } Execution of this program will produce the output as shown below: -0) 1) 2) 3)

Individual Sales figure = 12239.0 Individual Sales figure = 15027.5 Individual Sales figure = 12291.0 Individual Sales figure = 12907.0 Grand total of Sales = 52464.5 Average sales per person = 13116.125

Example 10.5 To Compare first or last element with other Elements of an array /* First element of an array is compared with all other elements one by one and the result of comparison – lower or higher – is printed out */ public class CompareDemo { public static void main() { int a[] = {12,34,10,27,9,39}; for (int i=0; i<5; i++) { if ( a[0] < a[i+1]) { System.out.println (" 0-th element is lower than "+ (i+1)+ "-th index element."); } else System.out.println (" 0-th element is higher than "+ (i+1)+ "-th index element."); } } } By executing this program you can observe the output as ---0-th element is lower than 1-th index element. 0-th element is higher than 2-th index element. 0-th element is lower than 3-th index element. 0-th element is higher than 4-th index element. 0-th element is lower than 5-th index element.

In this example an array a[ ] is traversed sequentially to access different elements. Such sequential access can easily be controlled by for-loop statement. We will now see how sequential or linear search for any particular element (may be called – key) in an array can be performed. Example 10.6 To Search for a particular element in an Array /* Searching sequentially for the key = 45 in the array b [10] */ public class SearchingDemo { public static void main() { int b[] = {5,3,1,8,9,45,23,81,75,29}; int key = 45; int found = 0; int i; for ( i=0; i<10; i++) { if (key = = b[i]) {found =1; break; } } if ( found = = 1) System.out.println ("The element is found at position " + (i+1)); else System.out.println ("The element is not in the array."); } } If you run this program, the output will be shown as – The element is found at position 6 Example 10.7 Inserting Element in an Array at any Random Position /* Only 3 elements at three different locations are inserted in an array c [8] */ import java.io.*; // importing IO Library classes public class InsertDemo { public static void main() throws IOException { String num1,num2, num3; int n1,n2,n3,i; int c[] = new int[8];

// activating keyboard for data entry InputStreamReader kb = new InputStreamReader (System.in); BufferedReader inval = new BufferedReader (kb); // To enter First value at index 6 System.out.print ("Enter First Integer = "); num1 = inval.readLine(); // readLine() takes input as a String n1 = Integer.parseInt(num1); // String is converted into Integer c[6] = n1; // To enter Second value at index 1 System.out.print ("Enter Second Integer = "); num2 = inval.readLine(); n2 = Integer.parseInt(num2); c[1] = n2; // To enter Third value at index 4 System.out.print ("Enter Third Integer = "); num3 = inval.readLine(); n3 =Integer.parseInt(num3); c[4] = n3; System.out.println (" Element inserted at index position 1: " + n2); System.out.println (" Element inserted at index position 4: " + n3); System.out.println (" Element inserted at index position 6: " + n1); } } In this example you find that three integer values are inserted at random positions, first at index position 6, second at index position 1 and third at index position 4. Other positions are kept vacant. Execute this program to see the output (Picture 10.1). Extend this program to fill up all the remaining vacant positions.

Picture 10.1

10.2 Sorting Algorithms

Sorting -- is a technique by which a list of numbers or words can be sorted either in ascending or in descending order. In ascending, numbers are arranged from lower to higher and for words from A to Z. In descending, numbers are arranged in higher to lower and for words from Z to A. Preparing merit list based on marks obtained is an example of arranging total marks per candidate in the descending order. Here two very common sorting algorithms will be discussed. First about the Selection sort and then about the Bubble sort. 10.2.1 Selection Sort This algorithm is most suitable when data values are placed in an array of single dimension. Here the smallest element is searched out and placed in the first index position (for ascending order) of the array by exchanging their respective locations. Next the smallest of the remaining elements is searched out and then placed in the second position. In this way all other remaining elements are searched out and placed in their respective positions maintaining proper order. In this sorting technique, the minimum element (of the unfixed list) is selected and placed in its appropriate position – one after another. Thus the unfixed list length gradually decreases along with the number of comparisons required. For this reason the name -- Selection or Selection-exchange Sort -- has been given to this algorithm. For sorting in the descending order, the largest element is searched and placed in the first index position. The process is looped until all the elements are arranged in the descending order. Two programs, one for ascending and another for descending, will now be shown. The algorithms will be explained thereafter. Example-10.8 Demo of the SELECTION SORT for Ascending Order public class SelectionSort { public static void main() { int a[] = {6,4,8,1,9,23,45,24}; // 8 elements in the list int size = a.length; int min, temp, position; for (int i=0; i<size; i++) { System.out.println (i +"-th Pass starts:"); min = a[i]; position = i; for (int j=i+1; j<size; j++) {

if (a[j] < min) {min = a[j]; position = j;

// position of minimum element located

} temp = a[i]; a[i] = a[position];

// Positions exchanged to place // Pass-minimum at its proper place

a[position] = temp; } System.out.println( "Positions exchanged with minimum = " + min); // Minimum w.r.t. to a particular Pass } System.out.println (" Ascending order list is ::"); for (int k=0; k < size; k++) System.out.print (a[k] + " "); } } By running this program you will see the output as: -0-th Pass starts: Positions exchanged with minimum = 1 1-th Pass starts: Position exchanged with minimum = 4 2-th Pass starts: Position exchanged with minimum = 6 3-th Pass starts: Position exchanged with minimum = 8 4-th Pass starts: Position exchanged with minimum = 9 5-th Pass starts: Position exchanged with minimum = 23 6-th Pass starts: Position exchanged with minimum = 24 7-th Pass starts: Position exchanged with minimum = 45 Selection Algorithm [Step-by-step method followed to reach the end solution] Begin; Step1: Store Array elements- a[N]; Find array size; initialize instance variables; Step2: Start Looping -- Find location of the smallest element in the array and then

Interchange the position of the smallest element with that found at a[0]; Step3: Find the location of the next smallest element from the sub-list of N-1 elements and interchange it with that found at a[1]. Step4: Go on repeating Step-3 for sub-lists of lengths N-2, N-3, .. .., 2 elements for placing the minimum of the respective-Pass at the proper location of the array. Step5: Print out the final sorted list; End. Now look at the output of example-10.8. After pass –0, minimum element (i.e. 1) gets the first position; after pass-1 next minimum (i.e. 4) gets the second position; and in this way.... the largest element (i.e. 45) gets the last position. Thus a sorted list in the ascending order is obtained and printed out. The same algorithm [instead of the minimum – the maximum value is to be considered in every pass] can be applied to obtain the list in descending order as shown in example-10.9. Example-10.9 Demo of Selection Sort for Descending Order public class DescendSelSort { public static void main() { int a[] ={ 76,54,23,96,44,39,55,80}; int max, temp, posn; int size = a.length; for (int i=0; i<size; i++) { max = a[i]; posn = i; for (int j= i+1; j<size; j++) { if (a[j] > max) { max = a[j]; posn = j; } } temp = a[i]; a[i] = a[posn]; a[posn] = temp; } System.out.println (" Array sorted in descending order::");

for (int k=0; k<size; k++) System.out.print (a[k] + " "); } } By running this program you will get the output as: --Array sorted in descending order:: 96 80 76 55 54 44 39 23 10.2.2

Bubble Sort

The Bubble sort is another sorting algorithm where two adjacent elements of a list is compared and exchanged if they are not in order. This comparison [to place smaller valued element on top] process is continued for the entire list until no further exchange is found possible. This completes a single pass in which the largest element gets its final position at the bottom of the list. In the second pass, the process of comparison and interchange between adjacent elements is continued up to the last but one position in the list, because the last position has already been filled up with the largest element in the first pass. After this pass, the second largest element gets the place in the second place from the bottom. The process continues until the smallest element gets the top most position in the list. You have seen bubbles to move up in a liquid. Consider the smallest element as a bubble in an array list. As a bubble moves up in a liquid, so a smaller element gradually moves up in such an array list when bubble sort is applied. The name bubble sort is given to this algorithm because of this behaviour of the method. Let us first examine a program on Bubble Sort. Example- 10.10 Bubble Sort Demo // Sorting Array in ascending order public class SortingDemo { public static void main() { int number[] = {25,18,3,28,11,15}; int size = number.length; for (int i=0; i<size-1; i++) { for (int j=i+1; j<size; j++) { if (number[i] > number[j])

// input & initialization

// compare adjacent elements

{int tmp = number[i]; number[i] = number[j]; number[j] = tmp; } }

//move lighter on top // One Pass ends,

// the largest element is placed at the bottom }

//repeat for remaining elements in the list

System.out.println (" The sorted list is:: "); for (int i=0; i<size; i++) {System.out.println (" "+ number[i]); } } }

// print the ordered list

By running this program you can see the output as – The sorted list is:: 3 11 15 18 smaller elements are gradually bubbling up 25 28 Let us now try to understand the algorithm of the Bubble Sort. Begin; Step-1: Array a[N]is read and stored; instance variables initialized; Step-2: Adjacent comparisons –a[0] with a[1] and placing smaller one on top is continued until a[N-1] < a[N] condition is reached. This is the first pass in which the largest element of the list is placed at the bottom. Step-3: Go on repeating Step-2 for sub-lists of N-1, N-2, N-3,....., 2 elements until the smallest element gets the top position of the array. There will be altogether (N-1) number of Passes to sort a list of size N. Step-4: Print the ordered list. End. Assignment – Rewrite the Bubble sort algorithm to sort an array in the descending order.

10.3 Searching in Sorted Arrays We have already seen in example-10.6 how to search out a particular element of an array that is not sorted. The method used there is known as linear search as the search for the wanted element is carried out, one after another, starting from one list end in a linear fashion. If the list size is small then such linear search may be practicable. For a very large size list, linear search becomes very time consuming. However, if the list remains sorted, the searching process becomes very efficient as you have seen in a Dictionary. In a Dictionary, words remain sorted alphabetically and that is why searching for any word from anywhere becomes so easy and quick. That is why to make searching efficient, lists to be searched are maintained in sorted order. Binary search is the technique, which can be applied on sorted lists only.

10.3.1

Binary Search

The element to be searched is often called -- the Key. In a binary search, the middle element of the list is taken out and compared with the key. If key value is lower than the middle element value, then the lower half portion of the list is only taken into consideration; otherwise the upper half portion is considered. This technique is continued until either the match with the key if found out or it is reported that the key is not present in the list. Before going into any further details, we will examine first one program implementing Binary Search. Example-10.11 Demo of Binary Search // Remember: Binary Search can be applied only on Sorted List public class BinarySearch { public static void main() { int a[] = {1,3,5,7,9,10,12,14,16,18,20}; //sorted list int size = a.length; int key = 12; int lb= 0, hb = size-1; // Array’s lower and higher positions int mid; int done =1; // flag indicates not found while ( lb <= hb) { {mid = (lb + hb)/2; // mid point setting if (key > a[mid]) // to search in higher half portion lb = mid + 1;

else if (key < a[mid]) // to search in lower half portion hb = mid -1; else {if (key ==a[mid]) // match found { System.out.println (key + " is found at position " + (mid+1)); done = 0; // flag indicating success break; } } } } if (done = = 1) System.out.println (key + " is not present in the list."); } } By running this program you can see the output as --12

(the search key) is found at position 7

Try with a different key value [either present or absent in the list] and observe what output do you obtain and why. Now let us try to understand its algorithm. Begin; Step1: Initialize lower_bound(lb), higher_bound(hb) and the done flag; Step 2: Step 3 :

while (lb <= hb) do Set mid = (lb + hb)/2; if (Key > a[mid]) then lb = mid + 1; else if ( Key < a[mid]) then hb =mid +1; else if (Key = a[mid]) print the position of the key in the array; Set success flag; break;

Step 4:

Repeat from the beginning of Step-3 to find the match;

Step 5:

When Success Flag not set -- report that the key is not present in the list.

End. (Compare the algorithmic steps with the program codes shown in example- 10.11) 10.4

The class Object – compatible with all class types

There is one special class, called Object, in Java. All other classes can be regarded as sub-classes of this Object class. This means that a reference variable of type Object can refer to the objects of any other class types. Since arrays can be implemented as classes, a variable of type Object can also refer to an array. Object class can be regarded as a superclass of all other classes in java. It defines a number of methods, which are mentioned below: Object clone() boolean equals( object) void finalize() Class getClass() int hashCode() void notifyAll()

... ... ... ... ...

String toString() void wait(long, int) void wait(long) void wait()

... ...

Creates a new object of the same type; Returns true if equal; Default finalize() method; Obtains a Class object; Returns the hash code; Resumes execution of all threads waiting; Returns a string that describes the object; Waits up to specified milli-sec & nanosec; Waits up to specified milli-sec; Waits on another thread of execution.

In BlueJ environment, you can see these methods displaced under the menu head “ inherited from object “ (Picture 10.2) when an object gets created from a defined class. From a class definition, many objects can be created because the superclass Object is capable of cloning itself by calling its clone () method. No further discussions on this topic will be made here to keep the beginners free from the burden of advanced concepts in java. However, how an array containing elements of different data types can be created using the class Object will be shown here as a demonstration only. Object [ ]A = new Object[4]; .... will create 4 {0,1,....,3} object references stored in an array A as its elements. Similarly, T [ ] = new T [ N ]{ v0,v1,v2,v3, ...., vN-1}; ... will create N array elements of data type T. Study of Example-10.12 can make this conception more clear to you. Picture 10.2

(method list –incomplete)

Example 10.12 Use of Object Class as Array’s Reference Type public class ObjectClassDemo { public static void main() { Object [ ] A = new Object[4]; A[0] = new String(" Java Object class"); A[1] = new int [100]; A[2] = new float [122]; A[3] = new String(" B.S.Rao."); int sizeA = A.length; for (int j=0; j<sizeA; j++) System.out.println (A[j]); System.out.println (); int [ ] B = new int[ ]{ 12,74,26,92}; int sizeB = B.length; for (int j=0; j<sizeB; j++) System.out.print (B[j] + " "); System.out.println (); double [ ] C = new double[ ]{ 34.12, 25.0,46.15,69.5, 91.75}; int sizeC = C.length; for (int j=0; j<sizeC; j++) System.out.print (C[j] + " "); System.out.println (); } }

Execution of this program will show the output :-Java Object class [I@162b556 // reference to the data stored as Integer [F@162b53a // reference to the data stored as Float B.S.Rao. 12 74 26 92 // integer type array elements 34.12 25.0 46.15 69.5 91.75 //double type array elements The Object type array is a reference type array and stores the references of the array elements. Since Strings are always stored as references to char arrays, they are displayed as it is, but references to integer and float values are nothing but addresses of the locations where they are stored. Therefore, those addresses are displayed as output. Remember that int and double type arrays behave as normal arrays. Advanced users may extract benefits out of these Object class methods. 10.5

Conclusions

This chapter has dealt with arrays and their applications in solving many day-to-day problems. Arrays are fixed size linear data structures from where elements can be retrieved by specifying their index value(s). With a good number of examples the importance of arrays have been shown. Sorting a list of values is very often required. Two sorting algorithms have been explained with examples. The advantage of binary search over sequential search has also been shown. The concept of superclass Object and its importance of the clone () and other methods has been touched upon for advanced users. How an array can maintain references to created objects has also been discussed.