For this week, here's the plan, Stan…
From the book, make each point, then discuss if it makes sense, possible times when it doesn't, and any potential trade-offs that might arise…
The take-away: To document your API properly, you must precede every exported class, interface, constructor, method, and field declaration with a doc comment, subject to one exception — for complex APIs which consist of multiple interrelated classes, it is often necessary to supplement the documentation comments with an external document describing the overall architecture of the API. If such a document exists, the relevant class or package documentation comments should include a link to it.
The take-away: The most powerful technique for minimizing the scope of a local variable is to declare it where it is first used.
The take-away: By using a standard library, you take advantage of the knowledge of the experts who wrote it and the experience of those who used it before you. A second advantage of using the libraries is that you don't have to waste your time writing ad hoc solutions to problems which may only be marginally related to your work.
One really good application for a sequential list [remember those?] is for sorting. Recall that a sequential list is one that uses an array as the internal representation, and that this is what's known as a dynamic array because we need to re-size when there aren't enough slots. Sorting a sequential list is a good way to learn about the various ways of sorting things, since a large number of sorting algorithms are in existence already. What are some examples?
So, the idea of sorting is really just putting a collection of items into some sort of arbitrarily
defined [user-defined] order. We can define our own sorting, simply by deciding what kind of a
comparison we wish to make. These are known as comparative sorting algorithms
. Since we
haven't touched on algorithm analysis in detail yet, we'll do a bit of hand-waving at it this week.
We'll get to that part next week. At any rate, it turns out that linked lists are a bit difficult
to do comparison sorting on, because they require iterators; sequential lists are much easier to
deal with in this context!
The XKCD comic has a tongue-in-cheek look at sorting.
This is the quintessential first sorting
algorithm for most data structures classes. For the
Bubble Sort, the idea is to compare two numbers that are next to each other in the list, starting at
the back of the array and moving to the front, and arranging each pair so that the lesser
of the pair is moved to the left side of the pair each time. You keep doing this until the
smallest-valued item is at the front of the list and the largest-valued item is at
the back of the list. When you have been through the list and no swaps are made, you are done. It's
called Bubble Sort, because the smallest values bubble up
to the front [or because the largest
values bubble up
to the back, depending on your point of view…].
We can use our implementation of intList to implement a bubble sorting algorithm. First
thing we need is some sort of comparison method that will swap two numbers. We can add a
new method to the intList class called swapIntsAt() which takes two indices
and moves them:
public void swapIntsAt( int index1, int index2 ) {
int temp = theList[index1];
theList[index1] = theList[index2];
theList[index2] = temp;
}
// let's define a "toString()" method while were here,
// so we have a way of printing the entire list
public String toString() {
String output = "";
for( int i = 0; i < size; i++ ) {
output += theList[i];
}
return output;
}
OK, now we have a way to swap two values in the list, so now we can make a sorting
class that uses the swapping method as part of a comparison. We'll call it [because we are just
SOOOOOO imaginative] the intSorter class. Here is the
code to implement it:
public class IntSorter {
// Our first pass at sorting, a simple bubble sort; we'll add more later
public static void bubbleSort( IntList listToSort ) {
for( // what goes here? ) {
// Track if a swap has been made
boolean swapped = false;
// [!] Iterate through all elements of the list
// starting at the end element and up to the
// i + 1 element
for( // what goes here? ) {
// [!] Swap if the two currently adjacent
// in the 2nd loop iteration are out of order
if( // what goes here? ) {
listToSort.swapIntsAt( // what goes here? );
swapped = true; // Mark that you've swapped
}
}
// It's time to return if you made no swaps
if( !swapped ) {
return;
}
}
}
// OK, let's test it out! Add 51, 23, 17, 43, and 31 to the list,
// print it out, then sort it and print it again
public static void main( String[] args ) {
IntList orgList = new IntList();
orgList.append(51);
orgList.append(23);
orgList.append(17);
orgList.append(43);
orgList.append(31);
System.out.println("Pre-sort: " + orgList.toString() );
bubbleSort( orgList );
System.out.println("Post-sort: " + orgList.toString() );
}
}
OK, that wasn't so bad…
Next along the line is another common sort that is simple to implement and works well with the IntList
class, so we can add that to our intSorter class. This is called the insertion sort
and it works much the same way as people do alphabetical sorting. You select one item from the group,
and it starts a pile. You select another one, and put it on the top or bottom of the first. Then you
select another, and insert that one in its proper location: on top, on the bottom, or between
the other two items. You keep going through the items, inserting them in their proper places, until
all the items have been inserted in the list. In the interest of saving time for review for the test,
we'll cover insertion sort next week.
Here is a web page that shows all the different sorting algorithms [or at least most of the best-known ones] side by side with different starting states. It's interesting to watch what happens and see the algorithms in action! There is also a fun YouTube video of sorting algorithms, which takes about six minutes to get through, and which shows LOTS of sorting algorithms [but sequentially so you can't compare them side-by-side]. It's located here. There is also one that lets you choose the algorithm, but which shows you the array index at the bottom as it moves around during the sort; you can find that one here.
Here's what we've covered so far this semester. Everything here will be potential test fodder, so you
should be knowledgeable about all of it. Remember the test is closed book, closed note, closed laptop,
closed neighbor, and closed Internet. This will all be done from your knowledge and memory! It is a
great chance for you to really show your chops
with the material!
Topics that might be on the test include everything we have touched on so far , including:
That's probably enough for the this week because of your test on Thursday. Next week, we'll get into more Algorithm Analysis! Oh!