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<T>
{
  public Vector<T> sort(Vector<T> a, Comparator<T> c);
}

public interface InPlaceVectorSorter<T>
{
  public void sort(Vector<T> a, Comparator<T> 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<C extends Comparable<C>>
  implements Comparator<C>
{
  public int compare(C a, C b)
  {
    return a.compareTo(b);
  } // compare(C,C)
} // ComparatorForComparables

Comparator<Integer> c = new ComparatorForComparables<Integer>;
InPlaceVectorSorter<Integer> testme = 
  new RolfSorter<Integer>;
Vector<Integer> vec = new Vector<Integer>;
... // 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<T> v, Comparator<T> 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<T> v, Comparator<T> 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