This week's project is a team project to add more functionality to the List and Vecclasses we built in previous weeks. The project is to add a sort() method to each data structure, that arranges the items of the structure into ascending order. However, because the List and Vec are fundamentally different data structures, we will use a different algorithm for each:
for each index i = 0 to n-2 {
a. Find minIndex, the index of the smallest item in the sub-vec [itemi through itemn-1].
b. Swap the items at index i and index minIndex.
}
The first repetition of the loop, we find the index of the smallest item in the Vec,
and swap that item with the item at position 0. The second repetition, we find the second smallest
item in the Vec, and swap that item with the item at position 1. And so on.
Each repetition, we find and correctly position one item in the list, so at the end of n-1
repetitions, all items have been correctly positioned into ascending order.
So if aVec == [55, 77, 33, 99, 11] and we call aVec.sort(), then after the first repetition, we have:
aVec == [11, 77, 33, 99, 55](The red value indicates the minimum value; the blue value indicates the value that was at its location, with which the red value was swapped.) After the second repetition, we have:
aVec == [11, 33, 77, 99, 55]After the third repetition, we have:
aVec == [11, 33, 55, 99, 77]After the fourth repetition, we have:
aVec == [11, 33, 55, 77, 99]and the list is now in ascending order.
This algorithm uses random access to exchange the value at index i with the value at index minIndex. It thus works reasonably well for vectors. (As your textbook shows, it can also be implemented for lists, but it requires additional pointer variables to track the various items in the list.)
for i = 1 to n-1 {
a. Iterate through the sublist {item0 ... itemi-1}, looking for itemj > itemi.
b. If such an itemj exists {
Adjust pointers as necessary to move the node containing itemi
from its original position to the position immediately before
the node containing itemj.
}
}
This algorithm effectively keeps a sorted sublist, and adds each new item to the right spot in the sublist.
After n-1 repetitions of the loop, that sublist contains all of the items in ascending order.
To illustrate, if aList == {55, 99, 33, 77, 11}, then after the first repetition of the loop, we have:
aList == {55, 99, 33, 77, 11}
(no change, because the sublist contained only 55, and 55 < 99). After the second repetition, we have:
aList == {33, 55, 99, 77, 11}
After the third repetition, we have:
aList == {33, 55, 77, 99, 11}
After the fourth and final repetition, we have:
aList == {11, 33, 55, 77, 99}
Because this algorithm effectively removes items from the sequence
and then reinserts them back into the sequence at a different location,
it works well with linked lists
(i.e., inserting and removing items from a List are O(1)
operations if the insertion/removal point is already known).
As indicated on the grade sheet, different members of your team are responsible for different methods. (See me for the teams for this project.)
Begin by writing a method to test your sort() method. The person responsible for a given operation is also responsible for its test-method. A part of your grade will be based on the thoroughness of your tests, which should sort a variety of different-sized structures (e.g., empty sequences, sequences with just 1 item, sequences with many items, ...) and item-arrangements (e.g., in-order sequences, reverse-order sequences, random-order sequences).
Once you have a strong testSort() method, then write your sort() method. I strongly encourage you to "design" your method by drawing a diagram of what you want to have happen. Once you have a diagram of what you want to happen, you are more likely to write code that actually does the right thing. (Trial and error is not a good debugging technique.)
If you get to the point where you cannot figure out what is wrong, use the debugger! The debugger is your friend!
On this assignment, you and your partner have the option of trying out pair programming. You should only do so if your schedules are compatible enough to allow both of you to work together several times before the due date.