Sorting encompasses two functions: the sort itself and an auxiliary swap function. You may overload either or both of these in C++ to act on different data types.
To sort parallel vectors, you need to pass all of the vectors into the sort function and call swap more than once -- once for each parallel vector.
Here is the pseudocode for a swap function:
BEGIN FUNCTION swap
INPUT x, y
OUTPUT x, y (values switched)
t = x
x = y
y = t
RETURN
END FUNCTION swap
Note how values for x and y come into the function, are switched via the local temporary variable, and then are output to the caller. (How do you output two changed arguments in C++?)
Here is the pseudocode for a bubble sort function using size_types and subscripting:
BEGIN FUNCTION good_bubble
INPUT vector, start, end
OUTPUT vector (elements in [start, end) are in sorted order -- descending)
loop = start
done = FALSE
AS LONG AS ((loop < end) AND (NOT done)) DO
done = TRUE
RANGE cur FROM start TO end-1 BY 1
IF (vector[cur] < vector[cur+1]) THEN
CALL swap PASSING vector[cur], vector[cur+1]
RECEIVING vector[cur], vector[cur+1]
done = FALSE
END IF
END RANGE
loop = loop + 1
END AS LONG AS
RETURN
END FUNCTION good_bubble
Note that the start position is inclusive and the end position is exclusive. Also note that the elements in the vector in the range [start, end) are going to be in descending (actually non-increasing) order because the neighbors are swapped when the left one is less than the right one:
... harp | hart | asp | actual | animate | inter | bale | cramp ...
^ ^
| |
cur -+ |
|
cur+1 --------+
harp < hart --> swap!
... hart | harp | asp | actual | animate | inter | bale | cramp ...
Note that as each phase/pass of the sort progresses, the smallest element (since the above version is a descending/non-increasing sort) is pushed along the swapping 'wave front' toward the end of the range of elements to be sorted. Because of that, we could end each pass of the inner loop one item shorter than the previous loop.
For example, given the initial data:
| a | b | c | d | e |
After a single pass the a element would have moved all the way to the end of the range:
| b | c | d | e | a |
Since this element is now in place (remember, the sort is placing the data into descending/non-increasing order!), we need not ever consider it again and can stop further passes through the range of elements just short of it.
And, after the second pass through the range, we'd have:
| c | d | e | b | a |
Now, the b element is in its proper place and need not be considered again in subsequent passes.
Another thing we could do to slightly improve the behavior of bubble sort is to note that we need not restart each inner loop back at the beginning of the range. We could pick up (on the second inner loop pass) at the end of the range and simply walk backwards (instead of forwards as we'd done the previous pass). On this pass, we'd need to compare the elements not at cur and cur+1, but rather at cur and cur-1. And, to move backwards, we'd not be incrementing cur by +1, but rather by -1 (i.e. decrementing).
For example, after the first pass on the data above, we had:
| b | c | d | e | a |
Instead of starting back at the beginning (element b), we could start at the end (element a) and compare to the previous (instead of following) element:
| b | c | d | e | a |
^---^ 'e' < 'a'? no, don't swap
| b | c | d | e | a |
^---^ 'd' < 'e'? yes, swap
| b | c | e | d | a |
^---^ 'c' < 'e'? yes, swap
| b | e | c | d | a |
^---^ 'b' < 'e'? yes, swap
| e | b | c | d | a |
Then, on the next pass (the third), we'd start from where we'd left off, but go in the opposite direction (+1 instead of -1). So this pass would process just like the first. In fact, every odd pass will move forward (+1) and compare cur to cur+1 and every even pass will move backward (-1) and compare cur to cur-1.
Notice that as we moved backward through the range on that second pass, the largest element (e) moved toward its proper place at the start of the range. This is analogous to how the a was swept toward its proper place at the end of the range on the previous pass. Therefore, we could combine the above two variations into a new, more powerful, variation: We can not only sort bi-directionally, but also eliminate one element from each end of the range on each pass through the range. So on each pass, the range becomes shorter and shorter and we also don't have to keep re-positioning ourselves to the start: the best of both worlds!
While these variations have practical benefits in terms of running time, the overall performance of bubble sort remains n2 comparisons and n2 swaps. Check this out in the appropriate lab.