DSA-Module-3-Arrays.pdf

Unit 3: ARRAYS Unit 3 Arrays Introduction Before we formally define an array, let’s consider the following problems. We want to write a Java prog...

Unit 3: ARRAYS Unit 3 Arrays Introduction Before we formally define an array, let’s consider the following problems. We want to write a Java program that reads five numbers, finds their sum, and prints the numbers in reverse order. In your previous programing subjects, you learned how to read numbers, print them, and find their sum. What’s different here is that we want to print the numbers in reverse order. We cannot print the first four numbers until we have printed the fifth, and so on. This means that we need to store all the numbers before we can print them in reverse order. Unit Learning Outcomes At the end of the unit, you will be able to: a. differentiate and understand the values of the different types of arrays b. discover how to manipulate data in a one-multi-dimensional and two- dimensional array c. learn how to search and sort an array Topic 1: One Dimensional Array Time Allotment: 4 hours Learning Objectives At the end of the session, you will be able to: a. declare and create arrays b. initialize arrays c. index array elements correctly d. access array values e. sort array elements in ascending and descending order f. search for specific element in an array 1  Unit 3: ARRAYS Activating Prior Knowledge What comes to your mind when you hear the word ARRAY? Write your answer on the empty boxes provided below. 3 Presentation of Contents An array is a collection (sequence) of a fixed number of variables called elements or components, wherein all the elements are of the same data type. There are 3 types of an array namely one-dimensional array, two- dimensional array and multi-dimensional array. One-Dimensional Array A one-dimensional array is an array in which the elements are arranged in a list form. Declaring a One-Dimensional Array The general form to declare a one-dimensional array is: dataType[] arrayName; //Line 1 where dataType is the element type. Because an array is an object, arrayName is a reference variable. Therefore, the preceding statement only declares a reference variable. Before we can store the data, we must instantiate the array object. 2  Unit 3: ARRAYS The general syntax to instantiate an array object is: arrayName = new dataType[intExp]; //Line 2 where intExp is any expression that evaluates to a positive integer. Also, the value of intExp specifies the number of elements in the array. When an array is instantiated, Java automatically initializes its elements to their default values. For example, the elements of numeric arrays are initialized to 0, the elements of char arrays are initialized to the null character, which is '\u0000', the elements of boolean arrays are initialized to false. You can combine the statements in Lines 1 and 2 into one statement as follows: dataType[] arrayName = new dataType[intExp]; //Line 3 The statement: int[] num = new int; declares and creates the array num consisting of 5 elements. Each element is of type int. The elements are accessed as num, num, num, num, and num. Below illustrates the array num. 0 0 0 0 Alternate Ways to Declare a One-Dimensional Array Java allows you to declare arrays as follows: int list[]; //Line 1 Here, the operator [] appears after the identifier list, not after the data type int. You should be careful when declaring arrays as in Line 1. Consider the following statements: int alpha[], beta; //Line 2 int[] gamma, delta; //Line 3 3  Unit 3: ARRAYS The statement in Line 2 declares the variables alpha and beta. Similarly, the statement in Line 3 declares the variables gamma and delta. However, the statement in Line 2 declares only alpha to be an array reference variable, while the variable beta is an int variable. On the other hand, the statement in Line 3 declares both gamma and delta to be array reference variables. Traditionally, Java programmers declare arrays as shown in Line 3. We recommend that you do the same. Accessing Array Elements The general form (syntax) used to access an array element is: arrayName[indexExp] where indexExp, called the index, is an expression whose value is a nonnegative integer less than the size of the array. The index value specifies the position of the element in the array. In Java, the array index starts at 0. In Java, [] is an operator called the array subscripting operator. Consider the following statement: int[] list = new int; This statement declares an array list of 10 elements. The elements are list, list,..., list. In other words, we have declared 10 variables of type int as shown below. The assignment statement: list = 34; stores 34 into list, which is the sixth element of the array list as shown below. Suppose i is an int variable. Then, the assignment statement: 4  Unit 3: ARRAYS list = 63; is equivalent to the assignment statements: i = 3; list[i] = 63; If i is 4, then the assignment statement: list[2 * i - 3] = 58; stores 58 into list, because 2 * i - 3 evaluates to 5. The index expression is evaluated first, giving the position of the element in the array. Next, consider the following statements: list = 10; list = 35; list = list + list; The first statement stores 10 into list, the second statement stores 35 into list, and the third statement adds the contents of list and list and stores the result into list. Specifying Array Size during Program Execution When you include a statement in a program to instantiate an array object, it is not necessary to know the size of the array at compile time. During program execution, you can first prompt the user to specify the size of the array and then instantiate the object. The following statements illustrate this concept (suppose that console is a Scanner object initialized to the standard input device): int arraySize; //Line 1 System.out.print("Enter the size of the array: "); //Line 2 arraySize = console.nextInt(); //Line 3 System.out.println(); //Line 4 int[] list = new int[arraySize]; //Line 5 The statement in Line 2 asks the user to enter the size of the array when the program executes. The statement in Line 3 inputs the size of the array into arraySize. During program execution, the system uses the value of the 5  Unit 3: ARRAYS variable arraySize to instantiate the object list. For example, if the value of arraySize is 15, list is an array of size 15. Array Initialization during Declaration Like any other primitive data type variable, an array can also be initialized with specific values when it is declared. For example, the following Java statement declares an array, sales, of five elements and initializes those elements to specific values: double[] sales = {12.25, 32.50, 16.90, 23, 45.68}; The initializer list contains values, called initial values, that are placed between braces and separated by commas. Here, sales = 12.25, sales = 32.50, sales = 16.90, sales = 23.00, and sales= 45.68. Note the following about declaring and initializing arrays: When declaring and initializing arrays, the size of the array is determined by the number of initial values in the initializer list within the braces. If an array is declared and initialized simultaneously, we do not use the operator new to instantiate the array object. Arrays and the Instance Variable length Recall that an array is an object; therefore, to store data, the array object must be instantiated. Associated with each array that has been instantiated (that is, for which memory has been allocated to store data), there is a public (final) instance variable length. The variable length contains the size of the array. Because length is a public member, it can be directly accessed in a program using the array name and the dot operator. Consider the following declaration: int[] list = {10, 20, 30, 40, 50, 60}; This statement creates the array list of six elements and initializes the elements using the values given. Here, list.length is 6. Consider the following statement: int[] numList = new int; This statement creates the array numList of 10 elements and initializes each element to 0. Because the number of elements of numList is 10, the value of numList.length is 10. Now consider the following statements: numList = 5; numList = 10; 6  Unit 3: ARRAYS numList = 15; numList = 20; These statements store 5, 10, 15, and 20, respectively, in the first four elements of numList. Even though we put data into only the first four elements, the value of numList.length is 10, the total number of array elements. Note: Once an array is instantiated, its size remains fixed. In other words, if you have instantiated an array of 5 elements, the number of elements of the array remains 5. If you need to increase the size of the array, then you must instantiate another array of the desired size and copy the data stored in the first array into the new array. In the next section, we show how to copy the elements of one array into another array. Processing One-Dimensional Arrays Some basic operations performed on a one-dimensional array are initializing the array, reading data into the array, storing output data in the array, and finding the largest and/ or smallest element in the array. If the data type of an array element is numeric, some common operations are to find the sum and average of the elements of the array. Each of these operations requires the ability to step through the elements of the array, which is easily accomplished by using a loop. Suppose that we have the following statements: int[] list = new int; //list is an array of size 100 The following for loop steps through each element of the array list, starting at the first element of list: for (int i = 0; i < list.length; i++) //Line 1 //process list[i], the (i + 1)th element of list //Line 2 If processing list requires inputting data into list, the statement in Line 2 takes the form of an input statement, such as in the following code. The following statements read 100 numbers from the keyboard and store the numbers into list: for (int i = 0; i < list.length; i++) //Line 1 list[i] = console.nextInt(); //Line 2 Similarly, if processing list requires outputting data, then the statement in Line 2 takes the form of an output statement. The following for loop outputs the elements of list: 7  Unit 3: ARRAYS for (int i = 0; i < list.length; i++) //Line 1 System.out.print(list[i] + " "); //Line 2 The following example shows how loops are used to process arrays. The following declaration is used throughout this example: double[] sales = new double; double largestSale, sum, average; The first statement creates the array sales of 10 elements, with each element of type double. The meaning of the other statements is clear. Also, notice that the value of sales.length is 10. Loops can be used to process arrays in several ways: 1. Initializing an array to a specific value: Suppose that you want to initialize every element of the array sales to 10.00. You can use the following loop: for (int index = 0; index < sales.length; index++) sales[index] = 10.00; 2. Reading data into an array: The following loop inputs data into the array sales. For simplicity, we assume that the data is entered at the keyboard one number per line. for (int index = 0; index < sales.length; index++) sales[index] = console.nextDouble(); 3. Printing an array: The following loop outputs the elements of array sales. For simplicity, we assume that the output goes to the screen. for (int index = 0; index < sales.length; index++) System.out.print(sales[index] + " "); 4. Finding the sum and average of an array: Because the array sales, as its name implies, represents certain sales data, it may be desirable to find the total sale and average sale amounts. The following Java code finds the sum of the elements of the array sales (total sales) and the average sale amount: sum = 0; for (int index = 0; index < sales.length; index++) sum = sum + sales[index]; if (sales.length != 0) 8  Unit 3: ARRAYS average = sum / sales.length; else average = 0.0; Using For Loop – One Dimensional Array class OnedimensionalLoop { public static void main(String args[]) { int[ ] a={10,20,30,40,50};//declaration and initialization System.out.println("One dimensional array elements are :\n"); for(int i=0;i