6: Arrays

What We Will Cover Reminders: Please silence all cell phones and pagers When class is over, please shut down your computer if it is on. Illuminations 6.1: Arrays 6.1.1: Using Lists for Data 6.1.2: Declaring and Allocating Arrays 6.1.3: Referencing Array Elements 6.1.4: Initializing Array Values 6.1.5: Processing Array Values in a Loop 6.1.6: Using the Enhanced for Loop with Arrays 6.1.7: Array Index Out of Range 6.1.8: Arrays and Objects 6.1.9: Summary Exercise 6.1 6.2: Arrays and Methods 6.2.1: Arrays Are Objects 6.2.2: Arrays as Method Parameters 6.2.3: Returning an Array 6.2.4: Command-line Arguments 6.2.5: Summary Exercise 6.2 6.3: Programming With Arrays 6.3.1: Using Arrays Interactively 6.3.2: Testing Array Equality 6.3.3: Searching an Array 6.3.4: Removing Elements 6.3.5: Inserting Elements 6.3.6: Sorting an Array 6.3.7: Binary Search 6.3.8: Summary Exercise 6.3 6.4: Multidimensional Arrays 6.4.1: Introducing Multidimensional Arrays 6.4.2: Declaring and Allocating 2D Arrays 6.4.3: Initializing 2D Arrays 6.4.4: Example: Creating a Table 6.4.5: Ragged Arrays 6.4.6: Summary Exercise 6.4 Wrap Up Due Next: A5-Paradise Roller (3/17/10) A6-Card Games (3/24/10) Illuminations Homework Questions? A5-Paradise Roller (3/17/10) Viewing Assignment Results and Solutions Blackboard Questions from last class? ^ top 6.1: Arrays Learner Outcomes At the end of the lesson the student will be able to: Declare and allocate memory for arrays Write code to initialize arrays Use arrays with loops ^ top 6.1.1: Using Lists for Data Often times we need to process a group of the same types of data For instance: Bank account transactions Salaries for employees in a company Test scores for a group of students Temperature data over some period of time Consider how we might process following student test scores: 90 95 87 89 98 With this data, we can calculate statistics like: Highest score Lowest score Average (mean) score Difference (deviation) of each score from the average We can write a program to read this data and make the calculations However, to calculate the difference from the mean, we need to first find the mean Thus, we have to process all the data twice: one to find the mean and another to calculate the difference of each score from the mean To process the data more than once, the best approach is to keep all the data in main memory Storing Lists of Data If we know there are 10 inputs, we can use 10 separate variables Using separate variables quickly becomes prohibitive as the list gets larger (100 scores) One way to store lists of data in main memory is to use arrays Array: a data structure that organizes a list of identically-typed variables such that each variable is accessed using an index ^ top 6.1.2: Declaring and Allocating Arrays The general syntax for declaring an array is: dataType[] arrayName; or dataType arrayName[]; Where: dataType: the data type of all the array items arrayName: the name you make up for the array For example, to declare an array named scores of type int: int[] scores; The syntax to allocate memory space for an array is: arrayName = new dataType[size]; Where: arrayName: the name of the array dataType: the data type of all the array items size: the number of data items the array can hold For example, to allocate memory for 5 items of the scores array declared above: scores = new int[5] You can combine the declaration and allocation in one statement like: int[] score = new int[5]; // Java style Which is equivalent to: int score[] = new int[5]; // C++ style This is like declaring 5 variables of type int numbered as: score[0], score[1], score[2], score[3], score[4] The value in brackets is called an index or subscript Individual values in an array are called items, elements The number of indexed variables in an array is the size of the array: The largest index is one less than the size The first index value is zero Arrays can be of any data type All the variables of an array are always of the same data type Known as the base type of the array Once allocated, you cannot change the number of elements ^ top 6.1.3: Referencing Array Elements As you can see from the new operator, an array is an object: int[] score = new int[5]; However, it is convenient to think of an array as contiguous slots in memory like this: scores =  [0] [1] [2] [3] [4] Each of the memory slots can hold one of the data types, in this case an int Each array element is referenced by name and an index inside of square brackets For instance: scores[3] = 98; In Java, the slots of arrays are numbered starting at 0, as shown below: scores =        98   [0] [1] [2] [3] [4] Thus, the assignment to the slot with index 3 is put into the fourth slot The index can be any integer expression int n = 2; score[n + 1] = 99; You can use an indexed array variable like any regular variable: score[0] = score[1] + 1; ^ top 6.1.4: Initializing Array Values You can assign a value to an array element any time after the array is declared: int[] score = new int[5]; score[0] = 90; score[1] = 95; score[2] = 87; score[3] = 89; score[4] = 98; Static Initialization You can also initialize array elements in the declaration statement Called static initialization Use a comma-separated list inside curly-braces int[] score = {90, 95, 87, 89, 98}; This statement produces the same array as the previous six statements The compiler counts the number of elements and allocates an array of the correct size Default Values Uninitialized array elements are assigned default values: Integer (byte, short, int, long): 0 Floating-point (float, double): 0.0 Character (char): '\u0000' Boolean: false Objects: null ^ top 6.1.5: Processing Array Values in a Loop Array processing is easily done in a loop A for loop is commonly used to process array elements For example, to initialize array elements to a known value: double[] scores = new double[5]; for (int i = 0; i < scores.length; i++) { scores[i] = 100; } Note the use of the length instance variable in the array loop One of the advantages of using a class type is that an array always knows how many elements it has allocated Displaying an Array Similarly, we can also use a loop to display the contents of an array: System.out.println("You entered:"); for (int i = 0; i < scores.length; i++) { System.out.println(scores[i]); } Initializing From the Keyboard We can also use a loop to initialize values from the keyboard This is shown in the example application below Note that the loop counter and array index counts from 0 to length - 1 Example of Initializing from the Keyboard 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.Scanner; public class ScoreReader { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print("Enter your scores.\n" + "Number of scores: "); int num = input.nextInt(); double[] scores = new double[num]; for (int i = 0; i < scores.length; i++) { System.out.print("Enter score " + (i + 1) + ": "); scores[i] = input.nextDouble(); } System.out.println("You entered:"); for (int i = 0; i < scores.length; i++) { System.out.println(scores[i]); } } } ^ top 6.1.6: Using the Enhanced for Loop with Arrays In addition to the standard for loop, Java provides an enhanced for loop This loop is specially designed to work with arrays and other collections of data In other languages, this loop is known as the foreach loop Syntax: for (dataType variableName : arrayName) { // statements to execute } Where: dataType: the data type of all the array items variableName: the name to use for each variable arrayName: the name of the array Note that you do not code initialization, test and increment statements Instead, you declare a variable that refers to each array element Within the loop, you use this variable to access each array element To understand how this works, lets look at an example Example of Enhanced for Loop int[] score = {90, 95, 87, 89, 98}; for (double aScore : score) { System.out.println(aScore); } Example Comparison to Regular for Loop int[] scores = {90, 95, 87, 89, 98}; for (int i = 0; i < scores.length; i++) { System.out.println(scores[i]); } ^ top 6.1.7: Array Index Out of Range A common error is using a nonexistent index For an array of length 5, the indexes are 0 through 4 An index beyond this is out of bounds Using an out of range index value produces an error message! ArrayIndexOutOfBoundsException For example, using the following code: 1 2 3 4 5 6 7 8 9 10 public class WeekDays { public static void main(String[] args) { String[] day = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}; for (int x = 0; x < day.length; x++) { System.out.println(day[x]); } } } Trying to use an index less than 0 or more than length - 1 causes an error ArrayIndexOutOfBoundsException ^ top 6.1.8: Arrays and Objects The elements of an array of objects are not actual objects, but rather references to objects This is an important point that can cause confusion Allocating an array of objects only allocates space for a reference to each object Space is not allocated for the actual object until you create the object and assign it to the array element For example, the following code declares an array of String object references String names [] = new String [4]; All the elements of the array are assigned a default value of null Actual objects are not assigned until the following lines: names [0] = new String("Hi"); names [1] = "Mom"; names [2] = someObject.toString(); The following diagram illustrates this point The analog in C/C++ is an array of pointers to objects However, Java automatically dereferences the pointers unlike C/C++ Thus it may seem like you are working with an array of actual objects rather than references to objects Example of An Array of Objects 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public class ArrayObjs { public static void main(String[] args) { String[] weekdays = new String[7]; weekdays[0] = "Unknown"; weekdays[1] = "Tuesday"; weekdays[2] = "Wednesday"; weekdays[3] = "Thursday"; weekdays[4] = "Friday"; for (int i = 0; i < weekdays.length; i++) { System.out.println(weekdays[i]); } System.out.println(); weekdays[0] = "Monday"; weekdays[5] = "Thursday"; weekdays[6] = "Friday"; for (String day : weekdays) { System.out.println(day); } System.out.println(); } } ^ top 6.1.9: Summary Arrays are convenient ways to process a list of data You declare an array with a single statement: DataType[] arrayName = new DataType[length]; Each array element is referenced by name and an index inside of square brackets You can use an indexed array variable like any regular variable: score[0] = score[1] + 1; You can initialize array elements individually with an assignment statement: score[0] = 90; A more convenient way is to use an initializer list: int score[] = {90, 95, 87, 89, 98}; You can use loops to assign values to an array and to display array values The programmer must be very careful to keep the array index within bounds Otherwise an error message will result ArrayIndexOutOfBoundsException Check Yourself What is an array? When should you use an array? What are the two ways of declaring an array? How do you access an array element? What are two ways that you can initialize array elements? How can you check the capacity of an array while your program is running? If an array named scores had 100 elements in it, what code would you write to display all the elements? What happens if you try to print the tenth item of an eight item array? ^ top Exercise 6.1 Take one minute to prepare an answer the following questions. Is it possible to create arrays of length zero? Given the following declaration: String[] word = new String[5] what is: the array name? the base type? The length of the array? the range of values an index accessing this array can have? the value of one of the elements of this array ^ top 6.2: Arrays and References Learner Outcomes At the end of the lesson the student will be able to: Pass arrays as arguments Use arrays in methods Return arrays from methods Obtain values from the array passed to the main method ^ top 6.2.1: Arrays Are Objects Just like other class types, an array variable is a reference For example, an array of doubles named prices is stored like this: As you can see there are two ways to view an array: as a collection of indexed variables as a single reference variable Arrays in most languages, such as C/C++, are reference types as well ^ top 6.2.2: Arrays as Method Parameters You can use an entire array as an argument to a method When passing the array as an argument, you use just the array name and no brackets: showArray(days); Within the method you can access the array elements For example: public static void print(int[] values) { System.out.println("You entered " + values.length + " numbers:"); for (int item : values) { System.out.println(item); } } Within the method, you can determine the array size from the length variable Changing Array Elements in Methods Recall that an array argument is actually a reference type Thus any action taken on the parameter is actually taken on the original argument This means you can change array elements in methods You can see this in the following example Example Changing Array Elements in a Method 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import java.util.Scanner; class ArrayInput { public static void main(String [] args) { Scanner input = new Scanner(System.in); System.out.print("How many items? "); int numItems = input.nextInt(); int[] data = new int[numItems]; fillUp(data); print(data); } // Fills an array with values from the keyboard public static void fillUp(int data[]) { Scanner input = new Scanner(System.in); for (int i = 0; i < data.length; i++) { System.out.print("Enter number " + (i + 1) + ": "); data[i] = (int) input.nextDouble(); } } // Displays an array to the screen public static void print(int[] values) { System.out.println("You entered " + values.length + " numbers:"); for (int item : values) { System.out.println(item); } } } ^ top 6.2.3: Returning an Array Methods can return an array reference You can see this in the following example Example Returning an Array 1 2 3 4 5 6 7 8 9 10 11 12 public class ArrayMaker { public static void main(String arg[]) { char[] vowels = makeVowelsArray(); for(char ch : vowels) System.out.println(ch); } public static char[] makeVowelsArray() { char[] vowelArray = {'a', 'e', 'i', 'o', 'u'}; return vowelArray; } } ^ top 6.2.4: Command-line Arguments Recall that every Java application must have a method called main() public static void main(String[] args) { } Notice that the parameter args is an array of Strings Arguments are passed to the program by the operating system All words after the class name passed in the args array: java ArgEcho Java Rules! Number of parameters can be determined from args.length: System.out.println(args.length); args is a parameter of type String[] Example of Processing Command-line Arguments 1 2 3 4 5 6 7 8 public class ArgEcho { public static void main(String[] args) { for (int i = 0; i < args.length; i++) { System.out.print("Arg " + i + ": "); System.out.println(args[i]); } } } Produces the output: >java ArgEcho Hi Mom! Arg 0: Hi Arg 1: Mom! ^ top 6.2.5: Summary You can pass an array to a method A method may return an array Can change the array element within a method body: Because arrays are reference types Location of the array passed to the method When an element is accessed, the original location is used Operating system sends arguments to the String[] parameter of method main Can access these elements like any other array Check Yourself What is the header for a method named "showArray" that accepts an integer array? If the fillUp() method has an array parameter, and you change elements of the array inside the method, what happens to those changed elements when the method returns? What is the header for a method named makeArray() that accepts no parameters but returns a char array? The main() method has a String[] parameter. For a program named ArgEcho, what would you type at the command line to pass the values "hello" and "world" to the program? ^ top Exercise 6.2 Take one minute to prepare an answer the following question: What is wrong with the following method definition? public void doubleSize(int[] a) { a = new int[a.length * 2]; } An array length must be a literal integer and cannot be created from a calculated expression. The length of the array a is unknown when declaring the new array. Parameter a already has an array assigned and you cannot assign a new value to parameter a. The code is useless because parameter a goes out of scope when the method returns. ^ top 6.3: Programming With Arrays Learner Outcomes At the end of the lesson the student will be able to: Test array equality Compute statistics on arrays of data Search an array Sort an array Choose the best algorithm for searching an array ^ top 6.3.1: Using Arrays Interactively The size of an array is known as its dimension Sizing an array at run time is referred to as run-time dimensioning The following example uses a value read from the keyboard to allocate space for an array Example of Run-Time Dimensioning 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import java.util.Scanner; class ArrayInput { public static void main(String [] args) { Scanner input = new Scanner(System.in); System.out.print("How many items? "); int numItems = input.nextInt(); int[] data = new int[numItems]; fillUp(data); print(data); } // Fills an array with values from the keyboard public static void fillUp(int data[]) { Scanner input = new Scanner(System.in); for (int i = 0; i < data.length; i++) { System.out.print("Enter number " + (i + 1) + ": "); data[i] = (int) input.nextDouble(); } } // Displays an array to the screen public static void print(int[] values) { System.out.println("You entered " + values.length + " numbers:"); for (int item : values) { System.out.println(item); } } } Check Yourself When is the size of the array decided? What does the data array contain before the user enters any values? What is the value of data.length after one item has been entered? How do we know how many items have been entered by the user? ^ top 6.3.2: Testing Array Equality Remember that arrays are objects Thus, array variables are reference types Tests using == checks if the memory addresses are the same if (a == b) For example, what does the following code print? 1 2 3 4 5 6 7 8 9 10 11 public class ArrayChecker { public static void main(String[] args) { int[] a = {1, 2, 3}; int[] b = {1, 2, 3}; if (a == b) { System.out.println("a == b"); } else { System.out.println("a != b"); } } } Both arrays have the same elements However, they are stored at different locations in memory Thus, they do not have the same memory address Testing Array Elements for Equality To test array elements for equality, need to check each element Define an equals method that returns true if and only if all the array elements are equal Arrays must also be the same length Updating our original code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public class ArrayTester { public static void main(String[] args) { int[] a = {1, 2, 3}; int[] b = {1, 2, 3}; if (a == b) { System.out.println("a == b"); } else { System.out.println("a != b"); } if (equals(a, b) == true) { System.out.println("a equals b: "); } else { System.out.println("a not equal to b"); } } public static boolean equals(int[] a, int[] b) { boolean match = true; //tentatively if (a.length != b.length) { match = false; } else { for (int i = 0; i < a.length; i++) { if (a[i] != b[i]) match = false; } } return match; } } ^ top 6.3.3: Searching an Array Searching an array is about finding the index where a value is stored Many techniques for searching an array for a particular value Easiest technique is sequential search, whose algorithm is: Start at the beginning of the array Compare each value in sequence If the value is found, then return the index Continue until you reach the end of the array If no match is found, return -1 The following program defines a method that implements this algorithm Example of Searching an Array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.util.Scanner; public class ArraySearch { /** Finds the position of an item in an array. @param arr The array with the elements to search @param item The value to search for. @return The index of the first match, or -1 if not found. */ public static int find(int[] arr, int item) { for (int i = 0; i < arr.length; i++) { if (item == arr[i]) { return i; } } return -1; } public static void main(String [] args) { int[] arr = {12, -3, 9, -5, 10, 42}; for (int i = 0; i < arr.length; i++) { System.out.println(i + ": " + arr[i]); } Scanner input = new Scanner(System.in); System.out.print("\nEnter a search value: "); int key = input.nextInt(); int slot = find(arr, key); if (slot >= 0) { System.out.println("Found " + key +" in slot " + slot); } else { System.out.println(key + " not found"); } } } ^ top 6.3.4: Removing Elements Once we find an item in a list, we may want to remove it However, what does it mean to remove an element from an array? The problem with arrays in Java, and many other languages, is that the size of an array is fixed What we can do is shift the elements to overwrite the element we want to remove For instance, we could write a method like this: public static void remove(int[] arr, int pos) { for (int i = pos; i < arr.length - 1; i++) { arr[i] = arr[i + 1]; } } Note that the last element is now "extra" and must not be used When arrays have unused elements at the end, they are sometimes called partially-filled arrays The following diagram shows the remove operation Also, you can try the remove() method in example listed below Example Removing Elements of an Array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import java.util.Scanner; public class ArrayRemove { /** Removes an item from the vector preserving the order. @param arr The array with the elements to search. @param pos The number of the element to remove. */ public static void remove(int[] arr, int pos) { for (int i = pos; i < arr.length - 1; i++) { arr[i] = arr[i + 1]; } } // Test the remove method public static void main(String [] args) { // Zeros at end are unused space int[] arr = {12, -3, 9, -5, 10, 42, 0, 0}; for (int i = 0; i < arr.length; i++) { System.out.println(i + ": " + arr[i]); } Scanner input = new Scanner(System.in); System.out.print("\nEnter position to remove: "); int key = input.nextInt(); remove(arr, key); for (int i = 0; i < arr.length; i++) { System.out.println(i + ": " + arr[i]); } } } The problem with the remove() method shown above is that the array is the same size after removing the element What value should the last element have after it has been moved up? How can we solve this problem? Using arraycopy() Rather than using a loop, you can use arraycopy() System.arraycopy() is a method designed to copy array elements efficiently General syntax: arraycopy(src, srcPos, dest, destPos, length); Where: src: the source array srcPos: the starting position of the copy operation in the source array dest: the destination array destPos: the starting position of the copy operation in the destination array length: the number of elements to copy If the dest array is the same as the src array, the copy is made in the same array To see how to use arraycopy(), we rewrite our remove() method using arraycopy(): public static void remove(int[] arr, int pos) { int numItems = arr.length - (pos + 1); System.arraycopy(arr, pos + 1, arr, pos, numItems); } In this method, we are copying from pos + 1 to pos within the same array We specify the number of elements to copy using the formula: int numItems = arr.length - (pos + 1); ^ top 6.3.5: Inserting Elements If we want to insert an element into an array, we have to be careful about the last element If we shift elements up by one, that last element is overwritten and the data lost One solution is to use a partially-filled array to allow room for the last element Then only the data in an unused element is lost The following method uses this approach: public static void insert(int[] arr, int pos, int data) { for (int i = arr.length - 1; i > pos; i--) { arr[i] = arr[i - 1]; } arr[pos] = data; } Also, the following diagram shows the insert operation Growing an Array Another approach to inserting is to increase the size of the array by some number of elements before the insertion operation The insertion operation follows these steps: Increase the size of the array by a fixed amount, such as 1 Move all elements above the insertion location up by one slot Assign the value at the insertion location For example: public static int[] insert2(int[] arr, int pos, int data) { int[] newArr = new int[arr.length + 1]; for (int i = 0; i < pos; i++) { newArr[i] = arr[i]; } for (int i = pos; i < arr.length; i++) { newArr[i + 1] = arr[i]; } newArr[pos] = data; return newArr; } We show both these methods in the following example code Inserting Elements into an Array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 import java.util.Scanner; public class ArrayInsert { /** Inserts an item into an array, overwriting the last element. @param arr The array with the elements to search. @param pos The number of the element to remove. @param data The element to insert. */ public static void insert(int[] arr, int pos, int data) { for (int i = arr.length - 1; i > pos; i--) { arr[i] = arr[i - 1]; } arr[pos] = data; } /** Inserts an item into an array, growing the size of the array by one, and returning the new larger array. @param arr The array with the elements to search. @param pos The number of the element to remove. @param data The element to insert. @return A new array with the item inserted. */ public static int[] insert2(int[] arr, int pos, int data) { int[] newArr = new int[arr.length + 1]; for (int i = 0; i < pos; i++) { newArr[i] = arr[i]; } for (int i = pos; i < arr.length; i++) { newArr[i + 1] = arr[i]; } newArr[pos] = data; return newArr; } public static void main(String [] args) { // Zeros at end are unused space int[] arr = {12, -3, 9, -5, 10, 42, 0, 0}; for (int i = 0; i < arr.length; i++) { System.out.println(i + ": " + arr[i]); } Scanner input = new Scanner(System.in); System.out.print("\nEnter position to insert: "); int key = input.nextInt(); System.out.print("\nEnter value to insert: "); int data = input.nextInt(); insert(arr, key, data); // arr = insert2(arr, key, data); for (int i = 0; i < arr.length; i++) { System.out.println(i + ": " + arr[i]); } } } Performance of Insertions and Deletions When an array changes size, it is called a dynamic array Creating a new array, copying elements from the old array and deleting the old array takes computer time and memory The time and memory is proportional to the length of the array, or O(n) using big O notation To improve the performance of dynamic array, it is common to use a partially-filled array until the array is full When more capacity is needed in a filled array, the array size is increased Typically, array size is doubled when the capacity is increased To manage the array efficiently, you should encapsulate the array in a class Java has a library, called the Java Collections Framework, that includes dynamic arrays We will study dynamic structures, such as dynamic arrays, later in the course ^ top 6.3.6: Sorting an Array Sorting is a common task for computers, for example: Sort numbers in ascending order Sort numbers in descending order Sort strings in alphabetic order Many different algorithms for sorting, including: Bubble sort - move item up until in right place Insertion sort - add elements to list one at a time Selection sort - pick 1st, then 2nd, etc. Quick sort - divide and conquer Selection Sort Selection sort is one of the easiest -- but not the most efficient General algorithm: Find the smallest element Swap with the first element Find the smallest element in the rest of the list Swap with the first element of the rest of the list Repeat until the list is sorted Pass a[0] a[1] a[2] a[3] a[4] a[5] a[6] Original 10 7 29 14 -4 -12 21 First -12 7 29 14 -4 10 21 Second -12 -4 29 14 7 10 21 Third -12 -4 7 14 29 10 21 Fourth -12 -4 7 10 29 14 21 Fifth -12 -4 7 10 14 29 21 Sixth -12 -4 7 10 14 21 29 Selection Sort Code Following is selection sort code Have added some statements to show action for each pass 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 public class SelectionSort { public static void main(String [] args) { int[] a = {10, 7, 29, 14, -4, -12, 21}; System.out.print("Original array: "); print(a); sort(a); System.out.print("\nSorted array: "); print(a); } public static void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + ", "); } System.out.println(); } public static void sort(int[] a) { int index, indexOfMin; for (index = 0; index < a.length - 1; index++) { indexOfMin = findMin(a, index, a.length - 1); swap(a, index, indexOfMin); System.out.print("Pass#" + index + ": "); print(a); } } public static int findMin(int[] a, int start, int end) { int indexOfMin = start; for (int i = start + 1; i <= end; i++) { if (a[i] < a[indexOfMin]) { indexOfMin = i; } } return indexOfMin; } public static void swap(int[] a, int first, int second) { System.out.println("\nSwapping " + a[first] + " with " + a[second]); int temp = a[first]; a[first] = a[second]; a[second] = temp; } } Note that every element in the array must have a value Can the array have duplicate items? Also note that the larger task was broken into smaller tasks using methods Using methods helps to organize the program and improve clarity What About Bubble Sort? Another sorting algorithm that is easy to understand and use General algorithm: Make array.length passes through the array For each pass, compare each array element with the next element If the current element is larger than the next one, swap them Not an efficient sorting algorithm Sometimes simple algorithms perform poorly Simple algorithms are still useful because: easy to program and understand If better performance is needed, you replace them with a faster algorithm More information: Sorting Algorithms Includes Java source code Also: Sorting Algorithms ^ top 6.3.7: Binary Search Once an array is sorted, you can use binary search to find an item Binary search is much faster than sequential search Binary Search Algorithm A key value is searched for among the values stored in the array. Two index variables lowIdx and highIdx are used to limit the scope of the search. The search proceeds until the element searched for is found or the scope between lowIdx and highIdx is exhausted: The index middleIdx is computed as (lowIdx + highIdx) / 2. If key = data[middleIdx] the search is successful. If key < data[middleIdx], highIdx is lowered to middleIdx. If key > data[middleIdx], lowIdx is raised to middleIdx. If the scope between lowIdx and highIdx is exhausted, the search is unsuccessful. Demonstration applet: BinarySearch Binary Search Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import java.util.Scanner; public class BinarySearch { // find the index of key in array a // return -1 if key is not found public static int binarySearch(int[] a, int key) { int step = 0; int lowIdx = 0; int highIdx = a.length - 1; int middleIdx; while (lowIdx <= highIdx) { step++; middleIdx = (lowIdx + highIdx) / 2; System.out.println("Step#" + step + " lowIdx=" + lowIdx + " highIdx=" + highIdx + " middleIdx=" + middleIdx); if (a[middleIdx] == key) { return middleIdx; // just right } else if (a[middleIdx] < key) { lowIdx = middleIdx + 1; // too small } else { highIdx = middleIdx - 1; // too big } } return -1; // not found } public static void main(String [] args) { int[] data = {-12, -4, 7, 10, 14, 21, 29}; System.out.print("Searching array: "); for (int item : data) { System.out.print(item + " "); } System.out.println(); Scanner input = new Scanner(System.in); System.out.println("Enter a search value: "); int key = input.nextInt(); int slot = binarySearch(data, key); if (slot >= 0) { System.out.println("Found " + key +" in slot " + slot); } else { System.out.println(key + " not found"); } } } How Much Faster is Binary Search? Given the sorted array: a[0] a[1] a[2] a[3] a[4] a[5] a[6] -12 -4 7 10 14 21 29 How many steps to find the value of 14 using sequential search? How many steps to find the value of 14 using binary search? On average for an array of n elements: Sequential search takes n / 2 array accesses Binary search takes log2(n) - 1 array accesses Worst case for an array of n elements: Sequential search takes n array accesses maximum Binary search takes floor(log2(n)) + 1 array accesses maximum Translating to some array sizes: Array Size floor(log2(n)) + 1 1 1 10 4 100 7 1000 10 10,000 14 100,000 17 1,000,000 20 Binary search quickly becomes worth the effort of its implementation Binary search is one algorithm a programming professional should know! ^ top 6.3.8: Summary Arrays can be dimensioned at run time Also, you can easily enter values into an array for later processing When comparing arrays, you must be careful not to use the == operator The == operator returns true if two array reference refer to the same array The == operator does not determine if two seperate arrays have the same content To compare the content of two arrays, you can use a loop as we discussed: public static boolean equals(int[] a, int[] b) { boolean match = true; //tentatively if (a.length != b.length) { match = false; } else { for (int i = 0; i < a.length; i++) { if (a[i] != b[i]) match = false; } } return match; } We looked at several algorithms for use with arrays including: Linear search of an array for a specific value Removing an elementfrom an array Inserting an element into an array Sorting an array Binary search of a sorted array Check Yourself When is the size of the array decided: compile time or run time? After declaring an int array of 10 elements, and before assigning any values to the array, what value does each array element hold? If two separate arrays, array1 and array2, contain the same values, what does the following statement print? System.out.println(array1 == array2); If an int array named scores had 100 elements in it, what code would you write to find the index of the first occurrence of 98? Do all sorting algorithms take the same amount of time to sort arrays? What is binary search? Why is binary search faster than linear search on average? In what condition must all the elements of an array be to use binary search? ^ top Exercise 6.3 Take one minute to prepare an answer the following question: What would be the contents of the following array after each pass of SelectionSort? int[] array = {9, 21, -7, 2, 87, -19, 47} answer ^ top 6.4: Multidimensional Arrays Learner Outcomes At the end of the lesson the student will be able to: Use two-dimensional (2D) arrays Apply the techniques of 2D arrays to higher dimensions ^ top 6.4.1: Introducing Multidimensional Arrays Arrays in Java are objects Array elements can be objects, such as Strings Thus, array elements can reference other arrays This allows Java to have arrays of multiple dimensions String[] one; double[][] two; char[][][] three; Each added dimension requires one more pair of square braces We will focus on two-dimensional (2D) arrays in this section You then use similar techniques for multidimensional arrays Rows and Columns Two-dimensional (2D) arrays are like a spreadsheet or table First dimension is the row (by convention) Second dimension is the column Array elements are the intersection of a row and column For the array named data: data[0][0] data[0][1] data[0][2] data[1][0] data[1][1] data[1][2] ^ top 6.4.2: Declaring and Allocating 2D Arrays To declare as a 2D int array: int[][] data; or int data[][]; or even int[] data[]; You can allocate 2D arrays dynamically: int data[][]; // C-style data = new int[2][3]; or int[][] data = new int[2][3]; or int[][] data = new int[2][]; data[0] = new int[3]; data[1] = new int[3]; ^ top 6.4.3: Initializing 2D Arrays Like one-dimensional arrays, 2D array elements are assigned default values based on the array type: Integer (byte, short, int, long): 0 Floating-point (float, double): 0.0 Character (char): '\u0000' Boolean: false Objects: null You can initialize 2D arrays with static initializers or loops For example: 2 row by 3 column array using static initializers: int[][] data = {{1,2,3}, {4,5,6}}; You can process multi-D arrays by nesting loops Each loop has its own counter that corresponds to an index 1 2 3 4 5 6 7 8 9 10 11 12 public class Array2D { public static void main(String[] args) { int[][] data = {{1, 2, 3}, {2, 4, 6}}; for (int i = 0; i < data.length; i++) { System.out.print("Row " + i + ": "); for (int j = 0; j < data[i].length; j++) { System.out.print(data[i][j] + ", "); } System.out.println(); } } } Produces the output: Row 0: 1, 2, 3, Row 1: 2, 4, 6, ^ top 6.4.4: Example: Creating a Table Methods may have multi-D array parameters Methods may return a multi-D array as the value returned Similar to 1D arrays, but with more brackets Example: 2D int array of the multiplication table Example of a Two-Dimesnional Array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class MultTable { public static void main(String[] args) { int[][] table = makeTable(9); print(table); } public static int[][] makeTable(int size) { int[][] table = new int[size][size]; for (int i = 0; i < table.length; i++) { for (int j = 0; j < table[i].length; j++) { table[i][j] = (i + 1) * (j + 1); } } return table; } public static void print(int[][] table) { for (int i = 0; i < table.length; i++) { for (int j = 0; j < table[i].length; j++) { if (table[i][j] < 10) { System.out.print(" "); } System.out.print(table[i][j] + " "); } System.out.println(); } } } Notes on the Code Method makeTable returns a 2D table public static int[][] makeTable(int size) { Method print takes a 2D int array as a parameter public static void print(int[][] table) { ^ top 6.4.5: Ragged Arrays Ragged arrays have rows of unequal length Rows can have arrays assigned of different lengths Produces rows with different numbers of columns For example: int data[][]; data = new int[3][]; // allocate columns data[0] = new int[5]; // allocate row 0 data[1] = new int[0]; // allocate row 1 data[2] = new int[3]; // allocate row 2 Can also use static initialization and get the same result: int[][] data = {{1,2,3,4,5}, {}, {6,7,8}}; Example of a Ragged Array 1 2 3 4 5 6 7 8 9 10 11 12 public class ArrayRagged { public static void main(String[] args) { int[][] data = {{1,2,3,4,5}, {}, {6,7,8}}; for (int i = 0; i < data.length; i++) { System.out.print("Row " + i + ": "); for (int j = 0; j < data[i].length; j++) { System.out.print(data[i][j] + ", "); } System.out.println(); } } } ^ top 6.4.6: Summary Arrays can have more than one index Each index is called a dimension Thus, multidimensional arrays have multiple indexes, For example, an array with two indexes is a two-dimensional array. 2D array can be thought of as a grid or table with rows and columns: One index is for the row, the other for the column. Multi-dimensional arrays in Java are implemented as arrays of arrays, 2D array is a 1D array of 1D arrays. ^ top Exercise 6.4 Take one minute to prepare an answer the following question: Which one of the following 2D array declarations and initializations is not valid? int[] a[] = {{1, 2}, {1}, {}, {1, 2, 3, 4}}; int b[] = new int[2] {1, 2}; int[] c = new int[] {1, 0, 2, 3}; int d[] = new int[] {1, 2}; int e[][] = {{1,2}, new int[2]}; ^ top Wrap Up Due Next: A5-Paradise Roller (3/17/10) A6-Card Games (3/24/10) ^ top Home | Blackboard | Schedule | Room Policies | Syllabus Help | FAQ's | HowTo's | Links Last Updated: March 17 2010 @12:25:32