Exercising Your Array Management Skills
This topic will expose you to the bubble sort. In most cases, you don't have to memorize how it works, but you should definitely know how to implement the code if someone gives you the algorithm. In addition, the topic will use the bubble sort method as a vehicle to further support your understanding of references and how they can work inside and outside of a method. Here you go.
The bubble sort
There is no particular reason to study the bubble sort first but it is a fairly popular and well-known sorting process. The bubble sort has a couple of unique characteristics to it that will help you think about the possible cases of iteration actions. The pseudo code for a bubble sort is shown here.
set a Boolean called swapped to true
while( swapped is true )
{
set the swapped Boolean to false
set an index to zero
while( the index is two or more less than the number of items )
{
if( an item at one index is greater than the item at the next index up )
{
swap the two items
set the swapped Boolean to true
}
}
// end inner (swapping) loop
}
// end outer (list) loop
The name bubble sort comes from the fact that the higher values appear to "bubble", or "float" up to the top of the list. This sort, like the others that will be reviewed, has two nested loops, making these sorts fairly inefficient. Again however, the value of the sorts is more educational than actually usable in most real situations.
There are two ways to run a bubble sort. One is to run the outer loop as many times as there are items in the list less one. That way, every item will have an opportunity to "bubble up" to its appointed location, and the first item will have found its place when the other ones are sorted. Then the inner loop simply looks at each two contiguous items in order and if the first one is larger than the second one, it swaps them.
Now this leads to the second way to approach a bubble sort. If the inner loop makes it all the way through the list without swapping anything, then it is known that the list is properly sorted. So, the second way is to sort until no more swaps occur. So the outer loop simply repeats until no more swaps are conducted, and the inner loop simply goes through the list looking at pairs to swap, if needed. You will observe this next.
Shown below is an example of a fully reversed list being sorted by the bubble sort. First, look at the 'z' character being "bubbled up" from the lowest position. This inner loop must iterate N (i.e., the number of items in the list) times to move a letter from the beginning to the end of the list.
Start : zyxwv
Inner loop iteration 1 : yzxwv
Inner loop iteration 2 : yxzwv
Inner loop iteration 3 : yxwzv
Inner loop iteration 4 : yxwvz
Since some items were swapped, the outer loop will choose to run again. The inner loop process below shows the second pass at the "bubble" process for each letter.
Start : yxwvz
Inner loop iteration 1 : xywvz
Inner loop iteration 2 : xwyvz
Inner loop iteration 3 : xwvyz
Again, since some swaps occurred, the outer loop keeps working. The next example shows the process from the outer loop's perspective. First the 'z' is moved to the top, then the 'y', and so on.
Start : zyxwv
Outer Loop iteration 1 : yxwvz
Outer Loop iteration 2 : xwvyz
Outer Loop iteration 3 : wvxyz
Outer Loop iteration 4 : vwxyz
Outer Loop iteration 5 : vwxyz
The actual code for one version of the bubble sort is shown below.
/*
name: runBubbleSort_A
process: sorts characters using the bubble sort strategy
method input/parameters: characters in array (char[]), array size (int)
method output/parameters: sorted characters in array (char[])
method output/returned: none
device input/keyboard: none
device output/monitor: none
dependencies: none
*/
public void runBubbleSort_A( char[] letters, int arraySize )
{
// initialize method/variables
bool swapped = true;
int index;
// loop until no more swaps
while( swapped )
{
// set boolean to false and index to zero
swapped = false;
index = 0;
// loop until next to last item
while( index < arraySize - 1 )
{
// check for first one greater than second one
if( letters[ index ] > letters[ index + 1 ] )
{
// swap characters
// method: swapCharsByIndex
swapCharsByIndex( letters, index, index + 1 );
// set swapped flag
swapped = true;
}
// increment the inner loop index
index++;
}
// end inner (swapping) loop
}
// end outer (while swapped) loop
}
Notice that the loop must not iterate up to the last item since the two list elements tested are the one element and the element above it. It would cause an array boundary exception if you tried to test the index of the last item with the index of the item above it.
There are a handful of rather important items to discuss in the above method. The first one is that a while loop was used. The initialization(index = 0;), the condition to continue [while( index < arraySize - 1 )], and the updating action (index++;) are all colored in the code. The alternative to a while loop will be shown next.
About pass by copy, and references
However, the slightly less obvious condition is that the program is passing data back via the parameters instead of by returning anything. Note the method output/parameters line which states that the sorted array is being returned as one of the parameters. By Java specification, ALL data passed into a method via parameter is said to be pass by copy. This means that while the parameter itself might be changed inside the method, that same value will not be changed outside the method at completion. And as you read it, this definition is true. However, it's also a little bit of a fib. As mentioned previously, Java arrays are kind of like -- but not exactly like -- objects. One of the conditions they share with objects is that the identifier used for an array is a reference, or a pointer to where the data is in memory. As a reference, Java guarantees that it will not be changed outside the method after completion of the method.
HOWEVER, while the reference itself will not be changed, it is possible that the data to which the reference points CAN be changed. To Repeat: The reference or pointer to the where the data is in memory will not be changed. However, the data to which the reference points can be changed. Take a look back at the memory you observed previously.
|
A |
B |
C |
D |
E |
F |
G |
H |
|
|
1 |
(name) |
(age) |
(pay) |
(letters) |
--- |
--- |
--- |
|
|
2 |
--- |
--- |
--- |
--- |
--- |
--- |
--- |
--- |
|
3 |
--- |
--- |
'z' |
'y' |
'x' |
'w' |
'v' |
--- |
|
4 |
--- |
--- |
--- |
--- |
--- |
--- |
--- |
--- |
The reference, identified as letters but referencing, or pointed to, the memory location C3 will not change since Java's standard is to pass by copy and not change any parameters outside the method. However, the data referenced from C3 (i.e., 'z', 'y', 'x', 'w', and 'v') CAN be changed, and it will be in this sorting method.
But wait, there's more
In the method swapCharsByIndex, the same thing occurs. Consider the following.
/*
name: swapCharsByIndex
process: swaps characters within an array, given two index locations
between which to swap
method input/parameters: character array (char[]) index of one element (int),
index of other element (int)
method output/parameters: array with swapped elements returned (char[])
method output/returned: none
device input/keyboard: none
device output/monitor: none
dependencies: none
*/
public static void swapCharsByIndex( char[] arr, int indexOfOne, int indexOfOther )
{
// set temp to first item
char temp = arr[ indexOfOne ];
// set first to second
arr[ indexOfOne ] = arr[ indexOfOther ];
// set second to first with temp
arr[ indexOfOther ] = temp;
}
Here again, the reference to the array arr is passed in to the array, and as a reference, is unchanged. However, the elements of the array at indexOfOne and indexOfOther are changed. This is pretty handy considering there really wouldn't be much of another way to swap elements if it didn't work this way.
Another way to return the array
There are a couple of changes made to this method but it still accomplishes the same task. The first is that a for loop is used, and the second is that an array is created locally inside the method and then returned from the method. Consider the following code.
public char[] runBubbleSort_B( char[] letters, int arraySize )
{
// initialize method/variables
char[] localArr = new char[ arraySize ];
bool swapped = true;
int index;
// load array with input data
loadArray( localArr, letters, arraySize );
// loop until no more swaps
while( swapped )
{
// loop until next to last item
for( swapped = false, index = 0; index < arraySize - 1; index++ )
{
// check for first one greater than second one
if( localArr[ index ] > localArr[ index + 1 ] )
{
// swap characters
// method: swapCharsByIndex
swapCharsByIndex( localArr, index, index + 1 );
// set swapped flag
swapped = true;
}
}
// end inner (swapping) loop
}
// end outer (while swapped) loop
// return local array
return localArr;
}
To start with, notice that there are two initializations in the for loop (shown in red) that replace the individual initializations in the previous code; remember that this is okay to do, using a comma delimiter between them. Next however, note that a new array is created inside the method, it is loaded with the incoming data with the loadArray method which itself returns a changed (i.e., loaded) array via the parameter locaArr. Note that this method could have been implemented to return an array -- using a return action -- as well but it was decided to pass it back as a parameter.
Finally, just for completeness
This last example is the way the method could use the bubble sort strategy with an outer loop that iterates across all but one of the elements. It is not that much different, and it might be a little inefficient for an already partially sorted array, but the code is still interesting. Here you go.
/*
name: runBubbleSort_C
process: sorts characters using the bubble sort strategy
and outer loop that adapts to possibly previously sorted
array elements; array returns data via parameter
method input/parameters: characters in array (char[]), array size (int)
method output/parameters: none
method output/returned: sorted characters in array (char[])
device input/keyboard: none
device output/monitor: none
dependencies: swapCharsByIndex
*/
public char[] runBubbleSort_C( char[] letters, int arraySize )
{
// initialize method/variables
char[] localArr = new char[ arraySize ];
int listIndex, swappingIndex;
// load array with input data
loadArray( localArr, letters, arraySize );
// loop until no more swaps
for( listIndex = 0; listIndex < arraySize - 1; listIndex++ )
{
// loop until next to last item
for( swappingIndex = 0;
swappingIndex < arraySize - 1; swappingIndex++ )
{
// check for first one greater than second one
if( localArr[ swappingIndex ]
> localArr[ swappingIndex + 1 ] )
{
// swap characters
// method: swapCharsByIndex
swapCharsByIndex( localArr,
swappingIndex, swappingIndex + 1 );
}
}
// end inner (swapping) loop
}
// end outer (list) loop
// return local array
return localArr;
}
The bubble sort is the first of three you will be exposed to. It is not terribly efficient but it does have its own algorithmic character. Watch this video to see an animation of the process of sorting these letters. Another video is provided in the selection sort section that shows all three sorting actions as well as provides further support on returning results via the parameter list.
This chapter has also used the sorting method as a vehicle to provide more in depth information about how references work. Make sure you understand references. There will be more on these later . . .