Sequences, Iterators and Sorting

Sequences

Extends both array and node list.

Sequence Interface

/**
 * An interface for a sequence, a data structure supporting all
 * operations of a deque, indexed list and position list.
 */
public interface Sequence<E> 
     extends Deque<E>, IndexList<E>, PositionList<E> {
  /** Returns the position containing the element at the given index. */
  public Position<E> atIndex(int r) throws BoundaryViolationException;
  /** Returns the index of the element stored at the given position. */
  public int indexOf(Position<E> p) throws InvalidPositionException;
}

Implementation

Array or Link List, both are possible but the cost will be different:

• Link list requires counting to determine rank so atRank is linear time.  

• Array implementation uses an array of Position contianing both index and element.  Then rankOf can be implemented in constant time.  

Costs

Iterators

Class that cycles through all the elements of a container

For-each Loop

You are familiar with?

List<Integer> list;
for (Integer i : list)sum += i;

This a new syntax implemented in Java. How does Java do it?
First a new concept, an iterator.

Iterator Interface

interface Iterator {
  public boolean hasNext();
  public object next();
}

Example using an iterator to print container elements:

public static void printVector(java.util.Vector vec) {
         java.util.Iterator iter = vec.iterator();   // iterator for vector
         while (iter.hasNext()) {                       // using iterator
               System.out.println(iter.next());
         }
   }

Implementation

Two ways to make an iterator:

• Copy the elements of the container to an array or list, cost O(n).

• Traverse the container using a cursor, cost O(1) to make, but naturally O(n) to traverse.

  public class ElementIterator<E> implements Iterator<E> {
    protected PositionList<E> list; // the underlying list
    protected Position<E> cursor; // the next position
    /** Creates an element iterator over the given list. */
    public ElementIterator(PositionList<E> L) {
      list = L;
      cursor = (list.isEmpty())? null : list.first();
    }
    public boolean hasNext() { return (cursor != null);  }
    public E next() throws NoSuchElementException {
      if (cursor == null)
        throw new NoSuchElementException("No next element");
      E toReturn = cursor.element();
      cursor = (cursor == list.last())? null : list.next(cursor);
      return toReturn;
    }
  }

All most done. We need to tell Java that the contianer provides an iterator. This is done by extending iterable

Iterable Interface

public interface Iterable <E> {
   Iterator<E> iterator() // returns an iterator
}

Now Java can translate the for-each loop.

for (Integer i : list)sum += i;

is translated to

for (Iterator<Integer> it = list.iterator(); it.hasNext();){
   Integer i = it.next();
   sum += i;
}

Insertion Sort

An important part of this course is sorting.  We will learn many sorting algorithms. This first sort is one of the most important sorts.  

Algorithm

The algorithm iterates through the unsorted sequence and then searches through the sorted sequence to find the proper position to place the element.

Algorithm Sequence InsertionSort(Sequence X)
    make an empty Sequence S
    Iterator it← X.iterator()
    while it.hasNext() do
        Element e ← it.next()
        int i ← S.size-1
        // Find proper position in S
        while e < S[i] do i--
        S.addAfter(i)
    return S

Cost

What is the cost?  Consider the an array X in descending order then the inner most while loop will iterate through all of S.  The cost is

Σⁿ_i=1 i = i(i+1)/2 ∈ O(n²)

where X.size() = n.  So the worst case cost is quadratic.  Now consider that X is in ascending oder, i.e. sorted.  Then the inner while loop never executes, so the cost is O(n).  In other words the best case cost is linear.  Always the cost is O(n+k) where k is number of inversions, total number of times that the inner while loop executes.

In-place

In this case in-place means that we do not use a second array.  In-place has the advantage that less memory is used.  But more important all the data is kept in one place—this improves caching.

The basic idea of the algorithm is that we divide the array into two parts, a sorted part and an unsorted part.  An index mark the boundary of the two parts. As the algorithm searches for the proper position to place the new element it shifts elements of the sorted part.

Algorithm: InplaceInsertSort(Sequence S)

for insertIndex = 2 to S.size() do
      insertElem = S.atRank(insertI)
      sortIndex = insertIndex -1

      while insertElem < S.atIndex(sortIndex) and sortIndex > 0  do
             // find insert position and shift sorted elements right
             S.atIndex(sortIndex +1) = S.atIndex(sortIndex)
             sortIndex --

      S.atIndex(sortIndex +1) = insertElem  //insert element in position