CSC152 2005S, Class 50: Quadratic Sorts
Admin:
* Ringpops!
* How can you resist crystalline sugar with artificial flavor and color?
* Especially when it's attached to a hunka plastic that can wrap around your finger?
* For tomorrow: Think about the question at the end of this eboard.
Overview:
* Testing sorting
* Bubble sort
* Selection sort
* Insertion sort
* Can we do better?
Suppose we've written the following interfaces:
public interface OutOfPlaceVectorSorter
{
public Vector sort(Vector a, Comparator c);
}
public interface InPlaceVectorSorter
{
public void sort(Vector a, Comparator c);
}
Suppose that someone else writes a class that supposedly
implements one of these interfaces (your choice)
How would you verify that the sorter that they've written is
correct?
* You can assume that you only need to verify correctness
for Vectors of Integers
* We'll need to create a Vector to sort.
* We'll need to create something that can compare two Integers
* Nope, the folks at Sun didn't do it for us.
Detour: What should we do when we want to use Comparable objects (and their compareTo method), but or sorter expects a Comparator?
public class ComparatorForComparables>
implements Comparator
{
public int compare(C a, C b)
{
return a.compareTo(b);
} // compare(C,C)
} // ComparatorForComparables
Comparator c = new ComparatorForComparables;
InPlaceVectorSorter testme =
new RolfSorter;
Vector vec = new Vector;
... // Throw in a random buncha integers from 1 to 100
testme.sort(vec, c);
pen.println("The sorted vector is " + vec); // Not a bad idea, but ...
if (this.isSorted(vec, c)) {
pen.println("Rolf sorted the vector correctly.");
}
else {
pen.println("Rolf fails. Here's what he came up with when sorting: " + vec);
}
...
public boolean isSorted(Vector v, Comparator c)
{
for (int i = 0; i < v.size()-1; i++) {
if (c.compare(v.get(i), v.get(i+1)) > 0) {
return false;
} // if
} // for
// At this point, everything worked out okay.
return true;
} // isSorted(Vector v, Comparator c)
* QUestions
* In one stage of the tester, we have not verified that the result is a permutation of the original. How do we do it?
* Check the length
* Use an outofplace sorting algorithm and make sure that each element in the original vector appears the same number of times in the sorted vector.
* OR: Generate a sequence of numbers (e.g., 1, 2, 3, 4, 5, ...)
* CHoose a "random" starting point
* Choose a "random" increment (between 1 and 5)
* "Randomize" the original vector
* Run the same test LOTS AND LOTS of times
* Try different size vectors
* Also try: Already sorted (so we can just ask him to resort), Already "reverse sorted"
Techniques for Sorting
One sorting algorithm: Bubble sort
* Warning! Do not use it unless there is no other option (or you're told to)
* Idea: Repeatedly swap neighboring elements that are out of order.
* Running time: O(n^2)
* The constant multiplier is fairly large
Another sorting algorithm: Insertion sort
* Split the vector/list/whatever into two parts: Unsorted and Sorted
* Initially only the first element is sorted
* Initially everything else is unsorted
* Repeatedly take the first element of the unsorted portion and put it in the correct place of the sorted portion
[ 10 | 07 02 06 10 08 05 10 10 06 ]
[ 07 10 | 02 06 10 08 05 10 10 06 ]
[ 02 07 10 | 06 10 08 05 10 10 06 ]
[ 02 06 07 10 | 10 08 05 10 10 06 ]
[ 02 06 07 10 10 | 08 05 10 10 06 ]
[ 02 06 07 08 10 10 | 05 10 10 06 ]
* Running time:
* For one round:
* Finding the correct place to insert: b/c already sorted: O(log_2n)
* Inserting: O(n) to shift everything right
* There are n rounds:
O(n^2)
* More careful analysis:
First round: At most one swap
Second round: At most two swaps
Kth round: At most k swaps
Total number of swaps: 1 + 2 + 3 + ... + n-1
Sum: 1 + 2 + ... + m
Answer: (m * (m+1)) / 2
1 + 2 + 3 + ... + m/2
+ m + m-1 + m-2 + m/2+1
------------------------------
m+1 + m+1 + m+1 + m+1
m/2 columns, each of which sums to m+1, m/2*(m+1)
If m is odd, sum the first m-1 elements and then add m
(m-1)*m/2 + m = (2m + (m-1)m) / 2 = (m-1+2)m/2 = (m+1)m/2
Conclusion: Number of swaps is O(n*(n-1)/2) = O(n^2)
The final basic sorting algorithm: Selection sort
* Split array/vector into two parts: Unsorted and sorted
* Unsorted is initially empty
* Sorted is initially everything
* Repeatedly find the smallest thing in unsorted and put it at the end of sorted
[ | 10 07 02 06 10 08 05 10 10 06 ]
Putting 02 in the front means we had to move the 10 somewhere
and we crated a hole, so SWAP
[ 02 | 07 10 06 10 08 05 10 10 06 ]
[ 02 05 | 10 06 10 08 07 10 10 06 ]
[ 02 05 06 | 10 10 08 07 10 10 06 ]
[ 02 05 06 06 | 10 08 07 10 10 10 ]
Finding the smallest value in an array: O(n)
Repeated n times
O(n^2)
===
CAN WE DO BETTER? Yes! Divide and conquer