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 function as a vehicle to further support your understanding of pointers and how they can work inside and outside of a function. 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
Function input/parameters: characters in array (char[]), array size (int)
Function output/parameters: sorted characters in array (char[])
Function output/returned: none
Device input/keyboard: none
Device output/monitor: none
Dependencies: none
*/
void runBubbleSort_A( char letters[], int arraySize )
{
// initialize function/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
// function: 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 function. 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 red in the code. The alternative to a while loop will be shown next.
About pass by copy, and pointers
However, the slightly less obvious condition is that the program is passing data back via the parameters instead of by returning anything. Note the function output/parameters line which states that the sorted array is being returned as one of the parameters. By C specification, ALL data passed into a function via parameter is said to be pass by copy. This means that while the parameter itself might be changed inside the function, that same value will not be changed outside the function at completion. And as you read it, this definition is true. However, it's also a little bit of a fib. As mentioned previously, C array names are pointers. One of the conditions they share with objects is that the identifier used for an array is a pointer to where the data is in memory. As a pointer, C guarantees that it will not be changed outside the function after completion of the function.
HOWEVER, while the pointer itself will not be changed, it is possible that the data to which the pointer points CAN be changed. To Repeat: The pointer to where the data is in memory will not be changed. However, the data to which the pointer 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 pointer, identified as letters and pointing to the memory location C3 will not change since C's standard is to pass by copy and not change any parameters outside the function. However, the data pointed from C3 (i.e., 'z', 'y', 'x', 'w', and 'v') CAN be changed, and it will be in this sorting function.
But wait, there's more
In the function swapCharsByIndex, the same thing occurs. Consider the following.
/*
Name: swapCharsByIndex
Process: swaps characters within an array, given two index locations
between which to swap
Function input/parameters: character array (char[])
index of one element (int),
index of other element (int)
Function output/parameters: array with swapped elements returned (char[])
Function output/returned: none
Device input/keyboard: none
Device output/monitor: none
Dependencies: none
*/
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 pointer to the array arr is passed in to the array, and as a pointer, 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.
But wait, there's Um, more than one way to do this
It turns out that you actually can change parameters in C functions. As you know, arrays can be changed because they are pointers. So, what if you passed other data by pointer, or at least kind of like a pointer?
A new operation.There is an operator in C that can translate an address for a pointer. A pointer holds the address of some data in memory. The ampersand ( "&" ) operator can provide the memory address of a given value, as shown here.
int someVal = 15;
int *pointerToSomeVal = &someVal;
printf( "Value of someVal: %d, address of someVal: %ld\n",
someVal, (long)pointerToSomeVal );
While the pointer holds the address of some data, the ampersand operator can acquire the address from a variable that was not originally declared as a pointer. The results of the print statement are provided here.
Value of someVal: 15, address of someVal: 6422296
The value 15 is what is stored in the someVal variable, and the value 6422296 is the actual address of where that data is stored in memory. Pretty cool. So how can you use this to change data in functions. Take a look at the following function for swapping characters:
void swapChars( char *one, char *other )
{
char temp = *one;
*one = *other;
*other = temp;
}
Two things to note here:
- The function does not take in data, it takes in pointers, which as you know represent the addresses of the two values
- Inside the function the pointers are not exchanged. That is not allowed due to the pass by copy rules. However, the data pointed at by the two pointers can be exchanged, and that is how it is done
Now consider the format for calling this function. Because the function parameters are pointers, you cannot pass the data. However, you can pass the addresses of the two values which the pointers can work with. The function call looks like the following:
char charOne = 'A';
char charTwo = 'B';
swapChars( &charOne, &charTwo );
This is kind of handy. Now if you think back to the console and file I/O operations, you may remember the way that the functions scanf and fscanf were used. Take a look.
// initialize variables
int inputInt;
// prompt user for input
// function: printf
printf( "Enter your age: " );
// capture user response
// function: scanf
scanf( "%d", &age );
In this usage, the function scanf has two parameters, the string containing the data type to capture ( "%d", meaning "capture an integer" ), and the address of the variable ( age ) in which the data will be placed. By passing the address of the age, the scanf operation can set the value of age by placing the input-captured age value at the memory address where the variable age resides. As a note, the general term for getting data back from parameters is called pass by reference. Creating pointers in the functions, and then calling the functions with data addresses is a form of this.
Again, pretty cool, but important. Make sure you understand this process before you move on
Another way to return the array
There are a couple of changes made to this function 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 function and then returned from the function. Consider the following code.
char *runBubbleSort_B( const char *letters, int arraySize )
{
// initialize function/variables
char *localArr = (char *)malloc( arraySize * sizeof( char ) );
bool swapped = true;
int index;
// load array with input data (copies arrays)
// function: loadArray
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
// function: swapChars
swapChars( &localArr[ index ], &localArr[ index + 1 ] );
// set swapped flag
swapped = true;
}
}
// end inner (swapping) loop
}
// end outer (while swapped) loop
// return local array
return localArr;
}
More things to learn here:
- The original array is passed in as a const parameter. This is to protect the original array from being changed
- The function loadArray used to copy the original array into the locally created one. Supporting functions like this are useful. Note that this function 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. You always have choices
- The for loop initialization includes both setting the index to zero and setting the swapped flag to false. As you have seen previously, for loops support multiple initializations as well as multiple updating actions
- The elements of the localArr are passed with ampersand operators. Even here, you can capture the address of an array element and treat it just like any other variable
- The pointer to the array is returned to the calling function as you can tell from noting that the return type up above is char *. To repeat, you cannot pass arrays back from functions, but you can pass pointers and they can be pointed at an array
Finally, just for completeness
This last example is the way the function 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 does not adapt to partially sorted conditions
array elements; array returns data via parameter
Function input/parameters: characters in array (char[]), array size (int)
Function output/parameters: sorted characters in array (char[])
Function output/returned: none
Device input/keyboard: none
Device output/monitor: none
Dependencies: swapCharsByIndex
*/
void runBubbleSort_C( char letters[], int arraySize )
{
// initialize function/variables
int listIndex, swappingIndex;
// loop across N - 1 items
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( letters[ swappingIndex ]
> letters[ swappingIndex + 1 ] )
{
// swap characters
// function: swapCharsByIndex
swapCharsByIndex( letters,
swappingIndex, swappingIndex + 1 );
}
}
// end inner (swapping) loop
}
// end outer (list) loop
}
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 function as a vehicle to provide more in depth information about how pointers work. Make sure you understand pointers. There will be more on these later . . .