## 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 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(nr + 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
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
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");
}

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

 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
.