Suppose the list looked like:
Index | 0 | 1 | 2 | 3 | 4 |
Value | "ape" | "bat" | "cat" | "dog" | "elk" |
You wanted to switch the string at index 0 with the string at index 4 (i.e., switch "ape" for "elk"). After the swap, it looks like:
Index | 0 | 1 | 2 | 3 | 4 |
Value | "elk" | "bat" | "cat" | "dog" | "ape" |
How would you write Java code that would do this swap?
public void swap( ArrayList list ) { list.set( 4, list.get( 0 ) ) ; // LINE 1 list.set( 0, list.get( 4 ) ) ; // LINE 2 }Let's look carefully at LINE 1.
list.set( 4, list.get( 0 ) ) ;Recall that arguments must be evaluated first. In particular, we need to evaluate the second argument list.get( 0 ). This retrieves the object (handle) at index 0. This is "ape".
Thus, the method call is effectively:
list.set( 4, "ape" ) ;This sets the object at index 4 to "ape".
At this point, list looks like:
Index | 0 | 1 | 2 | 3 | 4 |
Value | "ape" | "bat" | "cat" | "dog" | "ape" |
If we run next statement,
list.set( 0, list.get( 4 ) ) ;and evaluate it:
list.set( 0, "ape" ) ;we end up with the same list as above. In any case, we've lost "elk", and we need to figure out how to avoid this.
public void swap( ArrayList list ) { Object temp = list.get( 4 ) ; // Save "elk" // MORE CODE TO BE ADDED }We fetched a copy of the handle to "elk" and put it in a local variable called temp. We know that "elk" is a String. In fact, temp has a handle to a String object. Why didn't we cast it to a String? We don't need to! All we plan to do is put this string at index 0. We don't intend to use it as a String (not yet, anyway).
Now that we've saved "elk", we can set the object at index 4 (which is currently holding "elk">) to the object at index 0 (which is currently holding "ape").
public void swap( ArrayList list ) { Object temp = list.get( 4 ) ; // Save "elk" list.set( 4, list.get( 0 ) ) ; // Put "ape" at index 4 // MORE CODE TO BE ADDED }So far, list still looks the same as before:
Index | 0 | 1 | 2 | 3 | 4 |
Value | "ape" | "bat" | "cat" | "dog" | "ape" |
public void swap( ArrayList list ) { Object temp = list.get( 4 ) ; // Save "elk" list.set( 4, list.get( 0 ) ) ; // Put "ape" at index 4 list.set( 0, temp ) ; // Put "elk" at index 0 }Now list is the way we wanted it.
Index | 0 | 1 | 2 | 3 | 4 |
Value | "elk" | "bat" | "cat" | "dog" | "ape" |
public void swap( ArrayList list, int firstInd, int secondInd ) { Object temp = list.get( firstInd ) ; list.set( firstInd, list.get( secondInd ) ) ; list.set( secondInd, temp ) ; }We can even do a little better because set() returns back the original element which it is about to overwrite. For example, if "ape" was at index 0, and we're about to overwrite it with "elk", the set() method returns "ape".
This allows us to write a shorter version:
public void swap( ArrayList list, int firstInd, int secondInd ) { Object temp = list.set( firstInd, list.get( secondInd ) ) ; list.set( secondInd, temp ) ; }Either this version or the previous one is acceptable.
If we made a method call and wanted to swap the elements at index 0 and index 4, we'd write:
foo.swap( list, 0, 4 ) ;This is an unusual method call because, frankly, we don't use the object foo. We don't refer to any instance variables, only parameter variables and local variables. In general, any method that doesn't use instance variables should be static.
Thus, it's better to write:
public static void swap( ArrayList list, int firstInd, int secondInd ) { Object temp = list.set( firstInd, list.get( secondInd ) ) ; list.set( secondInd, temp ) ; }If this were in class Foo, we'd write the method call as:
Foo.swap( list, 0, 4 ) ;Looks a lot like the version we had before, right? Except this time, Foo is a class. In the previous method call, foo was an object.
int temp = x ; x = y ; y = temp ;
Most sorting algorithms require swapping.