Tuesday, 2 July 2013

Sequences; bubble sort




Adapted from the Goodrich and Tamassia lecture on Sequences.
 Interface Container
 Interface java.util.Iterator
 
The Ranked Sequence ADT
  • The ranked sequence S (with n elements) supports the following methods:
    • elemAtRank(r):
Return the element of S with rank r; an error occurs if r < 0 or r > n – 1. Input: integer r; Output: Object
    • replaceElemAtRank(r, e):
Replace the element at rank r with e and return the old element; an error condition occurs if r < 0 or r > n – 1. Input: integer r; Output: Object
    • insertElemAtRank(r, e):
Insert a new element into S which will have rank r; an error occurs if r < 0 or r > n. Input: integer r, Object e; Output: none
    • removeElemAtRank(r):
Remove from S the element at rank r; an error occurs if r < 0 or r > n – 1. Input: integer r; Output: Object
Ranked Sequence Inheritance Diagram
 
 
 Interface RankedSequence
Array-Based Implementation
  • Some pseudo-code:
Algorithm insertElemAtRank(r,e)
    for i = n-1, n-2, …, r do
        S[i + 1] <---- S[i]
    S[r] ¬ e
    n <----n + 1 Algorithm removeElemAtRank(r):
    e <----S[r]
    for i = r, r+1, … , n-2 do
        S[i] <---- S[i+1]
    n <----n – 1
    S[i+1] ¬ null
    return e
O(n – r + 1)
= O(n) in the worst case of r = 0
= O(1) in the best case of r = n – 1 for removeMinElement or r = n for insertElemAtRank.
  • A graphical representation
insertElemAtRank(r,e):
removeElemAtRank(r):
Implementation with a Doubly Linked List
Consider the operation insertAtRank(1,"New York")
  • The list before insertion:
next = nodeAtRank(1);
prev = next.getPrev();
  • Creating a new node for insertion:

prev.setNext(newNode);
newNode.setPrev(prev);
newNode.setNext(next);
next.setPrev(newNode);
Implementation with a Doubly Linked List (cont.)
  • The list after insertion and before deletion:
  • Deleting a node: Let's say we call removeAtRank(2)
node = nodeAtRank(2);
prev = node.getPrev();
next = node.getNext();
  • after deletion
Ranked Sequence Inheritance Diagram
 Class NodeRankedSequence
Java Implementation
public class NodeRankedSequence extends MyDeque implements Deque, RankedSequence {
  public Object elemAtRank (int rank) {
        checkRank(rank);
    return nodeAtRank(rank).getElement();
  }
  public Object replaceElemAtRank (int rank, Object newElement)
                                                        throws BoundaryViolationException {
    checkRank(rank);
    DLNode node = nodeAtRank(rank);
    Object oldElement = node.getElement();
    node.setElement(newElement);
    return oldElement;
  }
Java Implementation (cont.)
      public void insertElemAtRank (int rank, Object element)
                                        throws BoundaryViolationException {
        if (rank != size()) // rank size() is OK for insertion
        checkRank(rank);
        DLNode next = nodeAtRank(rank); // the new node //will be right before this
        DLNode prev = next.getPrev(); // the new node will //be right after this
        DLNode node = new DLNode(element, prev, next);
        next.setPrev(node);
        prev.setNext(node);
        size++;
      }
Java Implementation (cont.)
    public Object removeElemAtRank (int rank) throws BoundaryViolationException {
        checkRank(rank);
        DLNode node = nodeAtRank(rank); // node to be //removed
        DLNode next = node.getNext(); // node after it
        DLNode prev = node.getPrev(); // node before it
        prev.setNext(next);
        next.setPrev(prev);
        size--;
        return node.getElement();
    }
Java Implementation (cont.)
    private DLNode nodeAtRank (int rank) {
        // auxiliary method to find the node of the element //with the given rank
        DLNode node;
        if (rank <= size()/2) { // scan forward from the head
            node = header.getNext();
            for (int i=0; i < rank; i++)
                node = node.getNext();
        }
        else { // scan backward from the tail
            node = trailer;
            for (int i=0; i < size()-rank ; i++)
                node = node.getPrev();
        }
        return node;
    }
    private void checkRank (int rank) throws BoundaryViolationException {
        if (rank < 0 || rank > size()-1)
            throw new BoundaryViolationException("Invalid rank.");
    }
}
Complexity of RankedSequence Methods
  • Comparison of array-based vs. doubly linked-list implementation of RankedSequence methods.
Method
Time
Array-based
Linked
size
O(1)
O(1)
isEmpty
O(1)
O(1)
elemAtRank
O(1)
O(n)
replaceElemAtRank
O(1)
O(n)
insertElemAtRank
O(n)
O(n)
removeElemAtRank
O(n)
O(n)
space
O(N)
O(n)
Note: In the doubly linked list implementation, method nodeAtRank is called from within methods elemAtRank, replaceElemAtRank, insertElemAtRank, and removeElemAtRank. Method nodeAtRank returns the node at the specified rank r and has complexity
.
For this reason, all of the methods that invoke nodeAtRank are O(n).
Nodes and Positions
  • Node-based operations:
    • Advantage: Node-specific methods, e.g. removeAtNode(Node v) and insertAfterNode(Node v, Object e) would be O(1).
    • Disadvantage: Node-based operations are not meaningful in an array-based implementation because there are no nodes in an array.
    • Dilemma:
      • If we do not include the node-based operations in the generic sequence ADT, we are not taking full advantage of doubly linked lists.
      • If we do include them, we violate the generality of object-oriented design.
Nodes and Positions (cont.)
  • Positions:
    • Intuitive notion of "place" of an element.
    • This concept allows us to enjoy doubly linked list without violating object-oriented design principles.
    • The Position ADT has two methods:
element(): Return the element at the Position.
Input: none; Output: Object   container(): Return the container that contains the position, or
throw an UnsupportedOperationException.
Input: none; Output: Container
    • Positions are defined relatively, i.e., in terms of their neighbors.
    • Positions are not tied to an element or rank.
    • A Sequence is a Container of elements that are each stored in a Position.
 Interface Position
PositionalContainer Inheritance Diagram
 Interface Container
 Interface PositionalContainer
PositionalSequence Inheritance Diagram
 Interface PositionalSequence
Sequence Inheritance Diagram
 Interface Sequence
Array Implementation of Sequence
  • It is not sufficient to merely store elements in the array, since the cells would have no way of accessing their corresponding positions.
  • Store Position references as array elements.
  • If implemented with a linear array, methods insertFirst, insertBefore, insertAfter, removeFirst, and remove would require O(n) operations because the position objects need to be shifted. The worst case would occur when removing or inserting to the front position. The methods insertLast and removeLast are O(1).
  • If implemented with a circular array, methods insertFirst and removeFirst are O(1). Methods insertBefore, insertAfter, and remove are O(n) but worst case occurs when .
NodeSequence Inheritance Diagram
 NSNode.java
 Class NodeSequence
Doubly Linked-List Implementation of Sequence – class NSNode
class NSNode implements Position {
    private NSNode prev, next; //# References to the //nodes before and after
    private Object element; //# Element stored in this //position
    private Container cont; //# Container of this position
    NSNode(NSNode newPrev, NSNode newNext, Container container, Object elem) {
        //# Initialize //the node
        prev = newPrev;
        next = newNext;
        cont = container;
        element = elem;
    }
    // Methods from interface Position
    public Container container() throws InvalidPositionException {
        if (cont == null)
        throw new InvalidPositionException("Position has no container!");
        return cont;
    }
Doubly Linked-List Implementation of Sequence - class NSNode (cont.)
    public Object element() throws InvalidPositionException {
        if (cont == null) throw new InvalidPositionException("Position has no container!");
            return element;
    }
    // Accesor methods
    NSNode getNext() { return next; }
    NSNode getPrev() { return prev; }
    void setNext(NSNode newNext) { next = newNext; }
    // Update methods
    void setPrev(NSNode newPrev) { prev = newPrev; }
    void setElement(Object newElement){ element = newElement; }
    void setContainer(Container newCont){ cont = newCont; }
}
 NSNode.java
Doubly Linked-List Implementation of Sequence – Class NodeSequence
public Position atRank (int rank) //# Return the position at the given rank
                throws BoundaryViolationException {    //# Thrown if rank<0 or rank > numElts-1
    checkRank(rank);
    // loop until find element at this rank
    NSNode current = head.getNext();
    for (int i = 0; i < rank; i++) {
        current = current.getNext();
    }
    return current;
}
public Position before (Position p) //# Return position before this one
            throws InvalidPositionException, BoundaryViolationException {
    NSNode n = checkPosition(p);
    NSNode prev = n.getPrev();
    if (prev == head)throw new BoundaryViolationException
                ("Cannot advance past the beginning of the sequence");
    return prev;
}
 
Doubly Linked-List Implementation of Sequence – Class NodeSequence (cont.)
public Position insertAfter (Position p, Object element) throws InvalidPositionException {
    NSNode n = checkPosition(p);
    numElts++;
    NSNode newNode = new NSNode(n, n.getNext(), this, element);
    n.getNext().setPrev(newNode);
    n.setNext(newNode);
    return newNode;
    }
public Position first() //# Return the first position in the sequence
            throws EmptyContainerException { //# Thrown if the sequence is empty
    if(isEmpty())
        throw new EmptyContainerException("Sequence is empty");
    return head.getNext();
}
Doubly Linked-List Implementation of Sequence – Class NodeSequence (cont.)
public Object remove(Position p) //# Remove this position from the sequence
                throws InvalidPositionException {
    NSNode n = checkPosition(p);
    numElts--;
    NSNode nPrev = n.getPrev();
    NSNode nNext = n.getNext();
    nPrev.setNext(nNext);
    nNext.setPrev(nPrev);
    Object nElem = n.element();
    // unlink the position from the list and make it invalid
    n.setNext(null);
    n.setPrev(null);
    n.setContainer(null);
    return nElem;
}
 NodeSequence.java
Comparison of Sequence ADT Implementations

Method(s)
Time Complexity
Circular Array
Doubly Linked List
size, isEmpty
O(1)
O(1)
atRank, rankOf, elemAtRank
O(1)
O(n)
first, last
O(1)
O(1)
before, after
O(1)
O(1)
replace, swap
O(1)
O(1)
insertElemAtRank, removeElemAtRank
O(n)
O(n)
insertFirst, insertLast
O(1)
O(1)
insertAfter, insertBefore
O(n)
O(1)
remove
O(n)
O(1)

 
Bubble Sort
A bubble sort works by scanning through a sequence and swapping a given element with the next one if the former is smaller than the latter.
 
Pass
Swaps
Sequence
   
{5,7,2,6,9,3}
1st
7« 2, 7« 6, 9« 3
{5,2,6,7,3,9}
2nd
5« 2, 7« 3
{2,5,6,3,7,9}
3rd
6« 3
{2,5,3,6,7,9}
4th
5« 3
{2,3,5,6,7,9}

 Lafore Bubble-Sort Applet
 
  • Here is an implementation of bubble-sort for an array-based sequence

    •    
     
    public void static bubbleSort1(IntegerSequence s)
    {
        int n = s.size();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n-i-1; j++)
                if(s.atRank(j).element.intValue() > s.atRank(j+1).element().intValue())
                    swap(s.positionAtRank(j), s.positionAtRank(j+1));
    }


Bubble Sort (cont.)
  • This implementation is designed for a sequence based on a doubly linked list.
    public void static bubbleSort2(IntegerSequence s)
    {
        int n = s.size();
        IntegerSequencePosition prec, succ;
        for(int i = 0; i < n; i++) // ith pass
        {
           prec = s.firstPosition();
          for(int j = 0; j < n-i-1; j++)
             {
             succ = s.after(prec);
             if(prec.element().intValue() > (succ.element().intValue())
                swap(prec,succ);
             else
                prec = succ;
             }
        }
    }



 
 

Analysis of Bubble-Sort
  • Assume that accesses to sequence elements and swaps are O(1).
  • Bubble-sort requires n passes. Designate i as the current pass number. i = 1,…,n.
  • In the ith pass, only the first n-i+1 elements of the sequence are considered.
Þ cost of ith pass = 
  • Cost of all n passes = .
  • Recall that .
  • Thus the overall cost of bubble-sort is
.
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)