Class 27: Sorting Indexed Collections

Held Monday, October 11, 1999

Overview

Notes

• Are there questions on the exam?
• I'm somewhat disappointed that most groups did not get code to me by 9 a.m. That makes discussion much harder.
• We may have prospectives visiting today.

Contents

• Indexed Collections
• Partition

Handouts

• Java Plus Data Structures, Chapter 4: Implementing Lists with Arrays.
• Notes on assignment 3
• Project files:
  • Photo.java

Summary

• Quicksort concluded: partitioning arrays.
• Assignment 3 due.
  • Notes are available.
• Assignment (due Wednesday): start on chapter 3 of Java Plus Data Structures.

Indexed Collections

Added after class. You can find a similar discussion in outline 25.

• There are many different perspectives on sorting.
  • Suppose we wanted to talk about sorting in terms of objects that can sort themselves.
• One thing to begin with is an interface that includes a ``sort yourself'' function.

  
  import Comparator;
  import IncomparableException;
  
  /**
   * Things that you can tell to sort themselves.
   */
  public interface Sortable {
    /**
     * Sort the contents of the thing using a comparator
     * to compare elements.
     * Pre: The elements can be compared.
     * Post: The elements are sorted.  Each element is no greater
     *   the the next element.
     * Post: No elements are added or deleted.
     *
     * @exception IncomparableException
     *   if there are pairs of elements that cannot be compared.
     */
    public void sort(Comparator compare)
      throws IncomparableException;
  } // Sortable()
  
  
  

• Next, it helps to define superclasses for the things we might sort. In class, we decided to start with something we might call an IndexedCollection.
  • You can create new ones of a certain size.
  • You can get a particular element given the index of that element.
  • You can set a particular element.
  • You can swap two elements.
• In my notes and in the exam, I call that class Array.

  
  /**
   * A objects of values which can be indexed by 
   * integers from 0 to size().  Basically, a wrapper
   * class for Java's built-in arrays.
   * 
   * @author Samuel A. Rebelsky
   * @version 1.0 of September 1999
   */
  public class Array {
    // +--------+--------------------------------------------------
    // | Fields |
    // +--------+
   
    /** The elements of the objects. */
    public Object[] objects;
  
    // +--------------+-------------------------------------------- 
    // | Constructors |
    // +--------------+
  
    /** 
     * Build a new array which holds up to n elements. 
     * Initially, each element is null.
     */
    public Array(int n) {
      objects = new Object[n];
    } // Array(int)
  
    /**
     * Build a new array which holds the specified 
     * set of elements.
     */
    public Array(Object[] elements) {
      objects = new Object[elements.length];
      for (int i = 0; i < elements.length; ++i) {
        objects[i] = elements[i];
      }
    } // Array(Object[])
   
    // +-----------+----------------------------------------------- 
    // | Accessors |
    // +-----------+
  
    /**
     * Get the ith element of the array.
     *
     * @exception ArrayIndexOutOfBoundsException
     *   For the obvious reasons.
     */
    public Object get(int i) {
      return objects[i];
    } // get(int)
  
    /**
     * Get the number of elements in the array.
     */
    public int size() {
      return objects.length;
    } // size()
  
    // +-----------+----------------------------------------------- 
    // | Modifiers |
    // +-----------+
  
    /**
     * Set the ith element of the array.
     *
     * @exception ArrayIndexOutOfBoundsException
     *   For the obvious reasons.
     */
    public void set(int i, Object value) {
      objects[i] = value;
    } // set(int, Object)
  
    /**
     * Swap the ith and jth elements of the array.
     * Included because it's commonly used during sorting.
     */
    public void swap(int i, int j) {
      Object temp = objects[i];
      objects[i] = objects[j];
      objects[j] = temp;
    } // swap(int,int)
  
  } // class Array 
  
  
  

• How do we build one of these that can sort itself?

  import Sortable;
  import Array;
  import Comparator;
  /**
   * Arrays that can sort themselves.
   */
  public class SortableArray 
    extends Array
    implements Sortable
  {
    public void sort(Comparator compare) {
      // ...
    } // sort(Comparator)
  } // class SortableArray
  

Partition

• As you may have noted, one of the most important aspects of the Quicksort algorithm is partitioning the collection into two parts.
• It's fairly obvious how you would partition a list: step through the list, creating two sublists as you go.
• It's less obvious how you partition a subarray.
• Here's the basic technique:
  • Assume the pivot is at the start of the subarray (if it's not, put it there).
  • Put a ``cursor'' at both ends of the array. The left cursor moves right, the right cursor moves left. You stop when they cross.
  • When the left cursor hits a smaller or equal element, it moves right. When it hits a larger element, it stops.
  • When the right cursor hits a larger element, it moves left. When it hits anything else, it stops.
  • Once the two cursors have stopped, swap and go on.
• There are some subtleties as to the order in which you move the cursors. You should attempt to identify these subtleties as you work on the exam.