>>Let's take a look at an example of a sorted ArrayList, as we continue our study of classes
with generics. Now sorted data plays a very important part in computer science, and if
you think about it that's pretty logical. Think of an old-fashioned phone book. You
know, one that's paper? All the data in that phone book is in sorted order. Would
you be able to find somebody's phone number in New York City if the phone book wasn't
sorted? No, of course not. By putting things in sorted order it makes it enormously easier
to search for them—and this is true in computer science too.
In computer science when things are sorted we can use a very powerful search strategy
called binary search. Here's how it works: You repeatedly probe the middle of the remaining
elements. If the target value you're looking for is smaller than the middle element, you
search only the lower half. If the target is equal to the middle element, then you've
found your result and you're done. If the target is bigger than the middle element,
then you search only the upper half. This is an unbelievably powerful strategy. Let
me show you an example. Let's talk about the efficiency here.
Suppose we're searching a list that has a million elements in it. Now a million elements
sounds like a lot of elements, but in the context of today's computer science this is
not an especially large group of data. The first probe removes half a million elements
from consideration. So you do one comparison and you know that a half of the million elements
aren't it. That's getting a good bang for your buck! Now the second probe only removes
a quarter of a million options, but still you're getting a lot of value here. The third
one will remove one hundred and twenty-five thousand. With just three probes, we've remove
eight hundred and seventy-five thousand choices out of a million. That is a tremendous increase
in efficiency over stepping through an Array one position at a time. That's called linear
search, and with that each probe would remove only one value-- so we could do as many as
a million probes. So this is really a fantastic strategy. But the thing is, binary search
only works with sorted data, and so having the data sorted is really, really important.
So the question then becomes how do we sort data?
Well if the data is already in an ArrayList, this is kind of a tricky problem. We're going
to address it in the next quarter of the class once we have nested loops available for our
use. But, there's another strategy that we can do now, and that is to insert the data
in such a way that it remains sorted while it's being inserted, and that's something
that's within our grasp at this point. Now the method signature for this will be void,
add, ArrayList string of list. So we're adding to an ArrayList of Strings our target string.
Let's talk a little bit about how the algorithm would work.
Well, first off we're going to need to use methods from the Java API, because our list
is an ArrayList of Strings. Now the first thing we probably want to look for is to see
if there is a method that does this. There are lots of methods in the API, so let's go
and take a look and see if anything looks promising. Here's the ArrayList class. I'm
going to scroll down until I find the methods, and we see right up that we have some add
methods. There are two of them, and then some add all methods (those are not the right ones).
So the first method adds an element at the end of the list, and the second one adds a
specified element at a specified position in the list. Well neither one of those is
saying anything about sorting. Now it's not a bad idea to actually click on these and
make sure you understand what it's doing. So, let's read all the instructions.
This inserts the specified element at the specified position in the list. It shifts
the element currently at that position, if there is any, and any subsequent elements
to the right by adding one to their indices. Huh, so that's sort of interesting. Notice
that we're going to get an index out of bound exception, which is Java's way of saying that
this just isn't going to work if the index is less than zero or is greater than size.
Now something to pay attention to here is that it was not greater than or equal to size—the
index being equal to size is actually OK. These are the kinds of boundary conditions
that you need to watch for very, very carefully when you're doing code.
So for all of our work reading the API, the thing we know at this point is that the API
doesn't have any way of keeping data in sorted order. So, our looking for one that adds it
in sorted order just didn't pan out. That happens sometimes. So what we have to do is
work with the tools that are in the API. Now that first add command, that one isn't going
to help us out, because that's just putting things at the end of the list. So unless our
data happens to magically, automatically always be in sorted order, that isn't going to work
either. So that second add method, the one with the index in it, that has to be the one
we want to use. So what we're going to need to do is find the correct index for the data
and then insert a new element at that index.
Now we need to make sure the method shifts data aside. Well guess what? It does, we just
read the Java API to know that. So then the question becomes how do we find the index?
This is a little trickier. There is a method in the String class that's called compareTo,
and we haven't used it before so now it's time to really talk about what this means.
It uses something called lexicographic ordering. Now this is kind of the same as alphabetical
order, but it's a little bit different. And the reason it's different is because uppercase
and lowercase letters are different in ASCII, and they aren't in English. So let's go back
and look at an ASCII table again and sort of refresh our memory on this.
Here's an ASCII table, and notice over here are our capital letters: capital A through
capital Z, and over here are our small letters -- little A through little Z. So the capital
letters come first. They're at smaller decimal values, which is what this leftmost column
is, than the smaller letters. So in other words-- capital A and little A are two different
things, and capital A comes before little A. So that's how lexicographic ordering is
different than alphabetical ordering.
So the way lexicographic ordering works is Strings are compared one character at a time
until a non-matching character is found. Now it starts from the left. Which makes sense,
that's similar to alphabetic ordering. If all the characters match then the length is
compared. Let's take a look at how all the details work here. So let's say we have a
String first which has Abby in it, and then a String second that has Abigail. Now we know
in alphabetic ordering that Abby would be before Abigail—let's see if that's true
in lexicographic ordering. So we're going to do first.compareTo(second).
Well what's going to happen is the capital A in Abby is going to be compared to the capital
A in Abigail. Both letters are the same. So then they compare an index one. The B in Abby
will be compared to the B in Abigail. Those letters are the same, and so we're still having
a zero here. Then we compare the second B in Abby to the I in Abigail. If you take the
number that the letter B represents and you subtract the number that the letter I represents,
this will be a negative number. And because it's negative that means Abby with come before
Abigail. So this is how lexicographic ordering works.
Let's look at another example. Now I'm using a little bit of different syntax here and
one you may not have seen before. It's actually legal to use double quote ABC double quote
where you would have a String identifier and use the compareTo method. This can be kind
of handy to know it sometimes. So let's see what happens when we compare ABC to ABCDE.
Well, the little A is compared to the little A first -- they match. The little B is compared
to the little B -- they match. The C is compared to the C -- they match. When all the characters
match like that and one of the Strings has ended, what Java does is it uses the difference
in length to determine the result. So it takes the length of ABC, which is three and subtracts
the length of ABCDE, which is five, which gives us a negative value. Remember that a
negative value means that ABC will come before ABCDE. So we know now that the shorter String
object comes first.
Now when Strings have all of the same characters and are the same length, then zero is returned.
So compareTo contains a negative number when the first String is less than the second one,
when it comes before. Zero when it's the same, positive when the first String is greater
than the second one. Now if all that is confusing remember that it's documented in the API.
It's a little bit hard to read, but you can do it. Let's take a look at what this method
would look like.
First we'll have public static void add, ArrayList String list, and String target. So that's
the signature we talked about earlier. Now what we need to do is we need to step through
the list one element at a time and see if we found the right place to insert it. So
we start with an index at zero, and we make sure that our index doesn't go greater than
the size of the list, which is list.size. Now inside that loop we compare list.getOfIndex,
so that's the String at that index to the target. If it's less than zero, what that
means is the value at that index comes before the target. Well in that case you want to
keep moving on, so we increment the index.
Now the first time that you find a value that's bigger than the target—well guess what?
That means you've found the place where you want to do your insertion. So to do the insertion
you use list.addIndex, target. So that's the add method we looked at in the Java API, and
then we return. Now what the return does is it takes us outside of this method -- so at
that point we know we're finished.
Now, if we get all the way through that while loop and we have not found a place where our
target value is smaller than one of the values in it that means we need to add it onto the
end. And so that's what's happening way down at the bottom, we have list.AddOfIndex and
target. Now if you think of what value index will have at that point, the index less than
list.size, that test has just failed. So that means the index is going to be equal to list.size.
Remember when we were looking at the API? We determined that that was actually a legal
condition, that's how you add things onto the end of the list. And so that's how you
keep a list in sorted order. So keep programming.