Java Programming: From Problem
Analysis to Program Design, 3e
Chapter 10
Applications of Arrays
class Arrays (API)
• Contains a number of static methods that can be used to work with arrays.
• The various methods accept arguments to work with arays:
– Arrays.sort(double[] arr) : sorts the array into increasing order
– Arrays.equals(double[] a, double[] b) : returns true if the arrays
are identical in size and values
– Arrays.fill(int[] arr, int n) : fills the array with ‘n’s
– Arrays.binarySearch(int[], -23) : returns the index of the first time
that -23 is found in the array. Returns -1 if the number is not found.
• Note that most of these methods are overloaded. For example, there is a
Arrays.fill() method to fill String, doubles, chars, etc.
• These methods are also overloaded to accept arrays of Objects. This allows
you to do things like compare two StudentRecord objects:
Arrays.equals(sr1, sr2);
– Of course, this does require that the equals method has been overloaded in your
StudentRecord clas.
• Now let’s turn to the class ArrayList
*** Collections: ArrayList
•
•
•
•
•
Recall how the size of an array is declared when you first instantiate the array. This is
an important and significant limitation. If your array is full and you then realize you
need to add an element to your array, you would be required to do something like
create a new array and then copy all elements of the old array to the new array. The
moment you need to add yet another element, you’d have to repeat this process. This
is very wasteful in terms of computing resources.
In the bad-old days, programmers would try to get around this by declaring an array of
size “much_bigger_than_I_will_ever_need” and simply keep track of the number of
elements currently being used by the array. Languages that support “collections” such
as Java, give us a much nicer tool.
In Java, we can use a class called ArrayList (API). This class allows us to store
arrays of objects, add elements, remove elements, and search for elements (and do a
couple of other things as well).
This class does not use array syntax with square brackets. Instead, it uses methods.
NOTE: ArrayList can NOT be used with primitive data types (int, double, etc).
Instead, you can use the wrapper classes Integer, Double, etc.
Some examples:
ArrayList<String> names = new ArrayList<String>();
ArrayList<StudentRecord> students = new
ArrayList<StudentRecord>();
ArrayList<Double> numbers = new ArrayList<Double>();
StudentRecord s1 = new StudentRecord();
students.add(s1);
names.add("Lisa");
names.add("Max");
if (
names.contains("Max") ) { ...
//returns true
names.remove("Alan"); //nothing will happen
Simple ArrayList Example
public static void main(String[] args)
{
ArrayList<String> words = new ArrayList<String>();
words.add("hello");
words.add("goodbye");
words.add("test again");
for (int i=0; i<words.size(); i++)
System.out.print( words.get(i) + "\n");
} //end main
Note the method size() instead of the field ‘length’ that we typically use with arrays.
Note the method get() instead of the usual arrayName[] we used with arrays.
• *** Study and play with the file ArrayListPrac.java on
the class page.
• Note that an ArrayList can –usually does– hold objects.
The example here holds Strings, but you can easily have
lists of StudentRecords, Die, etc, etc
• Practice by creating a list of, say, Die objects and then
outputting them, searching through them, etc
• API is here.
• Note important methods such as:
– get(int)  returns an object at location of the int.
• E.g. get(0) will return the first item stored in the list
• e.g. System.out.println( list.get(2) ); will output the object at the 3rd
position in the list.
– size()  returns the size of the list
• Note: Your book spends some time
discussing a technique using something
called Vectors. This is a relatively dated
collections resource. You can skip this
section and focus on the ArrayList instead.
Algorithms
We’ve spent a good amount of time over the past 1.5 courses
learning about the syntax of programming. However, most of the
challenge and, yes, the fun of programming lies in coming up with
creative and efficient ways of solving problems. Today we will
spend some time trying to solve the problem of putting a list into
some kind of order. We will look at a couple of different
approaches to solving the problem (known as an algorithm) and
will attempt to gradually improve our algorithms in order to solve
our problem as efficiently as possible.
List Processing
• List: a set of values of the same type
– e.g. an array
• Basic operations performed on a list
–
–
–
–
Search list for given item
Insert item in list
Delete item from list
Sort list
Writing a method to search a list:
• Necessary information for our method:
– Array containing the list
– Length of the list
• Remember: Not every array is completely filled
– Item for which you are searching
• After search completed
– If item found, return an int representing the
location in array
– If item not found, return -1
Why not return a boolean?
In our discussion of the method (previous slide) note that the method
returns an int. Wouldn’t it make more sense to have a method that
looks for an item in an array return a boolean? Why an int??
The reason is that frequently when searching for an item in an array,
it’s not enough to simply know if the item is present, we also want to
know where in the array the item can be found. For this reason, it was
decided to write the method so that not only does the method tell us if
the item is indeed present, the method also tells us where the item is
located.
This is why the method does not simply return a boolean, but rather,
an int. This example also serves to illustrate how putting some
thought into the design of your methods can make them much more
useful.
Searching for an item
• Suppose that you want to determine whether 27 is in the list
• First compare 27 with list[0]; that is, compare 27 with
35
• Because list[0] ≠ 27, you then compare 27 with
list[1]
• Because list[1] ≠ 27, you compare 27 with the next
element in the list
• Because list[2] = 27, the search stops
• This search is successful
Search (continued)
• Let’s now search for 10 (not present in the
array)
• The search starts at the first element in the
list; that is, at list[0]
• Proceeding as before, we see that this time
the search item, which is 10, is compared
with every item in the list
• Eventually, no more data is left in the list to
compare with the search item; this is an
unsuccessful search
Search: the code
Search - continued
(Many ways to skin a cat)
Search (continued)
• Using a while (or a for) loop, the definition of the
method seqSearch can also be written without the break
statement as:
* An Aside: break and continue
• The ‘break’ statement when executed in a loop (while, for, do) ,
causes flow to immediately exit the loop. Execution continues
immediately after the body of the loop.
• continue: Also is used within loops. However, instead of exiting
the loop, flow skips the remainder of the loop’s body. It then
returns to the top of the loop for another iteration.
• ** Some programmers feel that break and continue are poor
examples of properly structured programming. We won’t delve
into these issues here, but do be aware that use of break /
continue is somewhat contraversial.
Sorting Our Lists (arrays)
Consider the simple search we’ve just talked about. For an array of
1000 items, a search will require a minimum of 1 comparison (if the
item is found in the very first element of the array) to a maximum of
1000 comparisons (the item is not present in the array).
Statistically, for an array of 1000 items, searches will require an
average of 500 comaprisons. When you consider that some arrays
can be much, much larger than 1000 items and also that we may
sometimes need to do many, many searches, this can add up to a
very slow application.
If we know that we are going to need to do lots of searching, it
would be a highly useful investment of time to sort our array in
order (e.g. alphabetic, or numeric). Sorting arrays is an important
technique in programming, so we will spend some time on it now.
Sorting a List
• There are many sorting algorithms out there, we will
begin with one known as the “bubble sort”.
• Bubble sort
– Go ahead and read the points here, but it will make much more
sense after studying the illustrations on the following slides
– Suppose list[0...n - 1] is a list of n elements, indexed 0
to n - 1
– We want to rearrange; that is, sort, the elements of list in
increasing order
– The bubble sort algorithm works as follows:
• In a series of n - 1 iterations, the successive elements, list[index]
and list[index + 1] of list are compared
• If list[index] is greater than list[index + 1], then the
elements list[index] and list[index + 1] are swapped, that
is, interchanged
Bubble Sort
Bubble Sort (continued)
Bubble Sort (continued)
Bubble Sort (continued)
• It is known that for a list of length n, on average
bubble sort makes n(n – 1) / 2 key comparisons
and about n(n – 1) / 4 item assignments
• Therefore, if n = 1000, then to sort the list
bubble sort makes about 500,000 key
comparisons and about 250,000 item
assignments.
• This amounts to ¾ of a million operations!
• In other words, this is hardly an efficient way of
sorting!
• Inefficiency = slow-running application
Selection Sort Algorithm
• The “selection sort” is another sorting
algorithm that has the advantage of being
much more efficient than the bubble sort
algorithm.
• List is sorted by selecting list element and
moving it to its proper position
• Algorithm finds position of smallest element
and moves it to top of unsorted portion of list
• Repeats process above until entire list is sorted
Selection Sort Algorithm - Pseudocode
Take a look at the code example on this slide. Note that is a
combination of programming syntax and English. This is known as
“pseudocode”.
Pseudocode technique is one of the VERY BEST ways you can
begin trying to come up with an algorithm to solve a problem.
You should be familiar with this term, and if I were to ask you to
give me an example of pseudocode in homework or exams, you
should be able to do so. The pseudocode used by the textbook for
the selection sort is replicated here:
for (index = 0; index < listLength-1; index++)
{
a. find the location, smallestIndex, of the smallest
element in the list array.
b. Swap the smallest element with list[index]. That
is, swap list[smallestIndex] with list[index].
}
Selection Sort (continued)
Selection Sort (continued)
Selection Sort (continued)
public static void selectionSort(int[] list,
int listLength)
{
int index;
int smallestIndex;
int minIndex;
int temp;
for (index = 0; index < listLength – 1; index++)
{
//find the location of the smallest element in the array
smallestIndex = index;
for (minIndex = index + 1;
minIndex < listLength; minIndex++)
if (list[minIndex] < list[smallestIndex])
smallestIndex = minIndex;
//swap the smallest element in the array with list[index]
temp = list[smallestIndex];
list[smallestIndex] = list[index];
list[index] = temp;
}
}
Selection Sort (continued)
• It is known that for a list of length n, on an
average selection sort makes n(n – 1) / 2 key
comparisons and 3(n – 1) item assignments
• Therefore, if n = 1000, then to sort the list
selection sort makes about 500,000 key
comparisons and about 3000 item assignments
• In other words, compare an average of 500,000
assignments in the selection sort with 750,000 in
the bubble sort.
• However, this is still quite high…
Insertion Sort
This is another algorithm that attempts to improve, yet again, the
efficiency of our sort. Here is the pseudocode as given in your
textbook:
for (firstOutOfOrder=1; firstOutOfOrder<listLength;
firstOutOfOrder++)
{
if ( list[firstOutOfOrder] is less than
list[firstOutOfOrder-1]
{
1. copy list[firstOutOrOrder] into temp
2. initialize location to firstOutOrOrder
3. do
{
a. move list[location-1] one array slot down
b. decrement location by 1 to consider the next element
sorted of the portion of the array
} while ( location>0 && the element in the upper list
at location-1 is greater than temp
4. copy temp into list[location]
Insertion Sort
• The insertion sort algorithm sorts the list by
moving each element to its proper place
Insertion Sort (continued)
Insertion Sort (continued)
Insertion Sort (continued)
Insertion Sort (continued)
public static void insertionSort(int[] list,
int listLength)
{
int firstOutOfOrder, location;
int temp;
for (firstOutOfOrder = 1;
firstOutOfOrder < listLength;
firstOutOfOrder++)
if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])
{
temp = list[firstOutOfOrder];
location = firstOutOfOrder;
do
{
list[location] = list[location - 1];
location--;
}
while(location > 0 && list[location - 1] > temp);
list[location] = temp;
}
} //end insertionSort
Insertion Sort (continued)
• It is known that for a list of length n, on average,
the insertion sort makes (n2 + 3n – 4) / 4 key
comparisons and about n(n – 1) / 4 item
assignments
• Therefore, if n = 1000, then to sort the list, the
insertion sort makes about 250,000 key
comparisons and about 250,000 item assignments
Searching
Now that we have sorted our lists, let’s return to a discussion of
searching.
Once we have an ordered list of items, we can significantly
improve the performance (efficiency) of our searching algorithms.
The two best known algorithms are the sequential search and the
binary search.
Sequential Search
This search begins by looking at the first item in the array, then the
second, then the third, etc, etc.
The advantage to having a sorted array is that the moment we get to
an item that is greater than the item we are searching for, we know
that the item must not be in the list and we can stop iterating
through the array.
Eg: We have an array: { 3 9 12 17 23 } and are looking for
the number 8. The moment we hit the second element in our array
(the 9), we know that 8 must not be present and can stop searching.
The code for a sequential search is shown on the next slide.
Sequential Ordered Search
public static int seqOrderedSearch(int[] list,
int listLength, int searchItem)
{
int loc;
boolean found = false;
for (loc = 0; loc < listLength; loc++)
if (list[loc] >= searchItem)
{
found = true;
break;
}
if (found)
if (list[loc] == searchItem)
return loc;
else
return -1;
else
return -1;
}
//Line
//Line
//Line
//Line
1
2
3
4
//Line 5
//Line 6
//Line
//Line
//Line
//Line
//Line
//Line
//Line
7
8
9
10
11
12
13
Binary Search
• Can only be performed on a sorted list
• We start half-way through our sorted list. If the the item
in the half-way array index is lower than the item we are
looking for, we continue searching, but in the upper
(later) half of the array only.
• Similarly, if the item in half-way array index is greater
than our search item, we can continue looking in the
lower half of the array only.
• We then repeat the process, dividing the array in half
each time.
• Sometimes called the “divide and conquer technique”
• Illustrations follow…
Binary Search Algorithm
• Search item is compared with middle
element of list
• If search item < middle element of list,
search is restricted to first half of the list
• If search item > middle element of list,
search second half of the list
• If search item = middle element, search is
complete
Binary Search Algorithm
(continued)
• Determine whether 75 is in the list
Binary Search Algorithm
(continued)
Binary Search Algorithm (continued)
public static int binarySearch(int[] list, int listLength,
int searchItem)
{
int first = 0;
int last = listLength - 1;
int mid;
boolean found = false;
while (first <= last && !found)
{
mid = (first + last) / 2;
if (list[mid] == searchItem)
found = true;
else
if (list[mid] > searchItem)
last = mid - 1;
else
first = mid + 1;
}
if (found)
return mid;
else
return –1;
} //end binarySearch
Binary Search Algorithm (continued)
Binary Search Algorithm (continued)
Performance of the Binary Search
Performance of the Binary Search
(continued)
Performance of the Binary Search
(continued)
• Suppose that L is a list of size 1000000
• Since 1000000  1048576 = 220, it follows that
the while loop in binary search will have at
most 21 iterations to determine whether an
element is in L
• Every iteration of the while loop makes two
key (that is, item) comparisons
Performance of the Binary Search
(continued)
• To determine whether an element is in L, binary
search makes at most 42 item comparisons
– On the other hand, on average, a sequential search will
make 500,000 key (item) comparisons to determine
whether an element is in L
• In general, if L is a sorted list of size n, to
determine whether an element is in L, the binary
search makes at most 2log2n + 2 key (item)
comparisons
Performance of the Binary Search (in English)
Ultimately, for an array of 1000 items, the maximum number of
operations turns out to be 11 !
Compare this with a maximum of 1000 in a sequential search.
String Class – Second look:
• Now that you have a pretty good if basic understanding of objects
and arrays, you will hopefully have little problems understanding
most or all of the methods in the String class.
• The slides that follow are a partial API of the String class. While
we will not cover these in any detail in class, you are expected to
be able to apply them if called upon (homework, exams, etc)
Additional String Methods
Additional String Methods (continued)
Additional String Methods
Additional String Methods
Effects of Some String Methods
Chapter Summary
• Lists
• Searching lists
– Sequential searching
– Sequential searching on an order list
– Binary Search
• Sorting lists
– Bubble Sort
– Selection Sort
– Insertion Sort
Chapter Summary (continued)
• Programming examples
• The class Vector
– Members of the class Vector
• The class String
– Additional methods of the class String
Descargar

Chapter 10