Arrays Pt. 2

The Arrays.binarySearch Method Since binary search is frequently used in programming, Java provides several overloaded binarySearch methods for searching a key in an array of int, double, char, short, long, and float in the java.util.Arrays class. For example, the following code searches the keys in an array of numbers and an array of characters. int[] list = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79}; System.out.println("Index is " + java.util.Arrays.binarySearch(list, 11));   char[] chars = {'a', 'c', 'g', 'x', 'y', 'z'}; System.out.println("Index is " + java.util.Arrays.binarySearch(chars, 't'));   For the binarySearch method to work, the array must be pre-sorted in increasing order. Return is 4 Return is ?4 (insertion point is 3, so return is -3-1) Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Sorting Arrays Sorting, like searching, is also a common task in computer programming. It would be used, for instance, if you wanted to display the grades from Listing 6.2, ?Assigning Grades,? in alphabetical order. Many different algorithms have been developed for sorting. This section introduces two simple, intuitive sorting algorithms: selection sort and insertion sort. Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Selection Sort Selection sort finds the largest number in the list and places it last. It then finds the largest number remaining and places it next to last, and so on until the list contains only a single number. Figure 6.17 shows how to sort the list {2, 9, 5, 4, 8, 1, 6} using selection sort. Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Selection Sort int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted 6 1 8 4 5 9 2 9 1 8 4 5 6 2 9 8 1 4 5 6 2 9 8 6 5 4 1 2 9 8 6 5 4 1 2 9 8 6 4 5 1 2 9 8 6 5 4 2 1 animation Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 From Idea to Solution for (int i = list.length - 1; i >= 1; i--) { select the largest element in list[0..i]; swap the largest with list[i], if necessary; // list[i] is in place. The next iteration applies on list[0..i-1] } list[0] list[1] list[2] list[3] ... list[10] list[0] list[1] list[2] list[3] ... list[9] list[0] list[1] list[2] list[3] ... list[8] list[0] list[1] list[2] list[3] ... list[7] list[0] ... Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Expand for (int i = list.length - 1; i >= 1; i--) { select the largest element in list[0..i]; swap the largest with list[i], if necessary; // list[i] is in place. The next iteration applies on list[0..i-1] } // Find the maximum in the list[0..i] double currentMax = list[0]; int currentMaxIndex = 0;   for (int j = 1; j <= i; j++) { if (currentMax < list[j]) { currentMax = list[j]; currentMaxIndex = j; } } Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Expand for (int i = list.length - 1; i >= 1; i--) { select the largest element in list[0..i]; swap the largest with list[i], if necessary; // list[i] is in place. The next iteration applies on list[0..i-1] } // Find the maximum in the list[0..i] double currentMax = list[0]; int currentMaxIndex = 0;   for (int j = 1; j <= i; j++) { if (currentMax < list[j]) { currentMax = list[j]; currentMaxIndex = j; } } Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Expand for (int i = list.length - 1; i >= 1; i--) { select the largest element in list[0..i]; swap the largest with list[i], if necessary; // list[i] is in place. The next iteration applies on list[0..i-1] } // Swap list[i] with list[currentMaxIndex] if necessary; if (currentMaxIndex != i) { list[currentMaxIndex] = list[i]; list[i] = currentMax; } Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Wrap it in a Method /** The method for sorting the numbers */ public static void selectionSort(double[] list) { for (int i = list.length - 1; i >= 1; i--) { // Find the maximum in the list[0..i] double currentMax = list[0]; int currentMaxIndex = 0;   for (int j = 1; j <= i; j++) { if (currentMax < list[j]) { currentMax = list[j]; currentMaxIndex = j; } }   // Swap list[i] with list[currentMaxIndex] if necessary; if (currentMaxIndex != i) { list[currentMaxIndex] = list[i]; list[i] = currentMax; } } } Invoke it selectionSort(yourList) Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Insertion Sort int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted The insertion sort algorithm sorts a list of values by repeatedly inserting an unsorted element into a sorted sublist until the whole list is sorted. Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Insertion Sort int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted 6 1 8 4 5 9 2 6 1 8 4 5 9 2 6 1 8 4 9 5 2 6 1 9 8 5 4 2 6 9 8 5 4 2 1 6 1 8 9 5 4 2 9 8 6 5 4 2 1 animation Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 How to Insert? The insertion sort algorithm sorts a list of values by repeatedly inserting an unsorted element into a sorted sublist until the whole list is sorted. Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 The Arrays.sort Method Since sorting is frequently used in programming, Java provides several overloaded sort methods for sorting an array of int, double, char, short, long, and float in the java.util.Arrays class. For example, the following code sorts an array of numbers and an array of characters. double[] numbers = {6.0, 4.4, 1.9, 2.9, 3.4, 3.5}; java.util.Arrays.sort(numbers);   char[] chars = {'a', 'A', '4', 'F', 'D', 'P'}; java.util.Arrays.sort(chars); Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Exercise 6.14 Bubble Sort int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted The bubble-sort algorithm makes several iterations through the array. On each iteration, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; otherwise, the values remain unchanged. The technique is called a bubble sort or sinking sort because the smaller values gradually "bubble" their way to the top and the larger values sink to the bottom. Iteration 1: 2, 5, 4, 8, 1, 6, 9 Iteration 2: 2, 4, 5, 1, 6, 8, 9 Iteration 3: 2, 4, 1, 5, 6, 8, 9 Iteration 4: 2, 1, 4, 5, 6, 8, 9 Iteration 5: 1, 2, 4, 5, 6, 8, 9 Iteration 6: 1, 2, 4, 5, 6, 8, 9 Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Two-dimensional Arrays // Declare array ref var dataType[][] refVar; // Create array and assign its reference to variable refVar = new dataType[10][10]; // Combine declaration and creation in one statement dataType[][] refVar = new dataType[10][10]; // Alternative syntax dataType refVar[][] = new dataType[10][10]; Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Two-dimensional Array Illustration Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Declaring, Creating, and Initializing Using Shorthand Notations You can also use an array initializer to declare, create and initialize a two-dimensional array. For example, int[][] array = new int[4][3]; array[0][0] = 1; array[0][1] = 2; array[0][2] = 3; array[1][0] = 4; array[1][1] = 5; array[1][2] = 6; array[2][0] = 7; array[2][1] = 8; array[2][2] = 9; array[3][0] = 10; array[3][1] = 11; array[3][2] = 12; int[][] array = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12} }; Same as Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Lengths of Two-dimensional Arrays int[][] x = new int[3][4]; A two-dimensional array is like an array or arrays Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Lengths of Two-dimensional Arrays, cont. int[][] array = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12} }; array.length array[0].length array[1].length array[2].length array[3].length array[4].length ArrayIndexOutOfBoundsException Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Ragged Arrays Each row in a two-dimensional array is itself an array. So, the rows can have different lengths. Such an array is known as a ragged array. For example, int[][] matrix = { {1, 2, 3, 4, 5}, {2, 3, 4, 5}, {3, 4, 5}, {4, 5}, {5} }; matrix.length is 5 matrix[0].length is 5 matrix[1].length is 4 matrix[2].length is 3 matrix[3].length is 2 matrix[4].length is 1 Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6 Ragged Arrays, cont. Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-222158-6