Breadth-First-Search & Depth-First-Search

1. Breadth-First-Search
BFS(G){
for (each vertex u in V[G] - {s}) {
color[u] = WHITE;
d[u] = ∞;
Pi[u] = NULL;
}
color[s] = GRAY;
d[s] = 0;
Pi[s] = NULL;
ENQUEUE(Q, s);

While (!Q.empty()){
u = DEQUEUE(Q);
for (each vertex v in adj[u]){
color[v] = GRAY;
Pi[v] = u;
d[v] = d[u] + 1;
ENQUEUE(Q, v);
}
color[u] = BLACK;
}
}

2. Depth-First-Search
DFS(G){
for (each vertex u in V[G]){
color[u] = WHITE;
Pi[u] = NULL;
}
time = 0;
for (each vertex u in V[G]){
if (color[u] == WHITE)
DFS-VISIT(u);
}
}

DFS-VISIT(u){
color[u] = GRAY;
time ++;
d[u] = time;
for (each vertex v in adj[u]){
if (color[v] == WHITE){
Pi[v] = u;
DFS-VISIT(v);
}
}
time++;
f[u] = time;
color[u] = BLACK;
}

B-Tree

1. Find key k in Tree T:
B-TREE-SEARCH(x, k){
int i = 1;
while (i <= n[x] && k > keyi[x] )
i++;
if (i <= n[x] && k == keyi[x]) return (x, i); else{ if (leaf[x])
return NIL;
else
return (ci[x], k);
}
}

2. Insert a node in Tree T;
3. Delete a node in Tree T;

Binary Search Tree

1. Search an element in Tree T:
1)Recursive Method:
TREE-SEARCH(root[T], k){
x = root[T];
if (x == NIL || key[x] == k)
return x;
else{
if (k < key[x])
return TREE-SEARCH(left[x], k);
else
return TREE-SEARCH(right[x], k);
}
}
2)Iterative Method:
ITERATIVE-TREE-SEARCH(root[T], k){
x = root[T];
while (x != NIL && key[x] != k){
if (k < key[x])
x = left[x];
else
x = right[x];
}
return x;
}

2. Find the minimal element in Tree T:
TREE-MINIMUM(root[T]){
x = root[T];
while ( left[x] != NIL)
x = left[x];
return x;
}

3. Find the maximal element in Tree T:
TREE-MAXIMAL(root[T]){
x = root[T];
while (right[x] != NIL)
x = right[x];
return x;
}

4. Find the successor of element x in Tree T:
TREE-SUCCESSOR(x){
if (right[x] != NIL)
return TREE-MINMIAL(right[x]);
else{
y = p[x];
while (y != NIL && x = right[y]){
x = y;
y = p[y];
}
return y;
}
}

QUICK-SORT

Input: A(p, r)

QUICK-SORT(A, p, r){
if (p < r){
q = PARTITION(A, p, r);
QUICK-SORT(A, p, q-1);
QUICK-SORT(A, q+1, r);
}
}

Subroutine:
PARTITION(A, p, r){
i = p -1;
x = A[r];
for (j = p; j <= r-1; j++){
if (A[j] <= x){
i++;
exchange(A[i], A[j]);
}
}
exchange(A[i+1], A[r]);
return i+1;
}

Features:
1. T(n) = O(nlgn) ~ O(n2)
2. Sort in place

HEAP-SORT

Input: A[]

Main Algorithm:
HEAP-SORt(A)
{
BUILD-MAX-HEAP(A);
for (int i = length[A]; i >=1; i--)
{
exchange(A[1], A[i]);
heap-size[A]--;
MAX-HEAPIFY(A, 1);
}
}

Subroutines:
BUILD-MAX-HEAP(A)
{
heap-size[A] = length[A];
for (int i = [heap-size[A]/2]; i >= 0; i--)
MAX-HEAPIFY(A, i);
}

MAX-HEAPIFY(A, i)
{
l = 2i;
r = 2i +1;
if (l <= heap-size[A] && A[l] > A[i])
largest = l;
else
largest = i;
if (r <= heap-size[A] && A[r] > A[largest])
largest = r;
if (largest != r)
{
exchange(A[i], A[largest]);
MAX-HEAPIFY(A, largest);
}
}

Bubble Sort

Input: A[]

for (i = 1; i <= length[A]; i++)
    {
         for (j = length[A]; j >=i; j--)
           {
              if (A[j] < A[j-1])
                   Exchange (A[j], A[j -1]);
           }
     }

Features:
1. Stable

Merge Sort

Input: A[], p, r, where p < r.

Merge-Sort(A, p, r)
{
if ( p < r )
{
q = [(p + r)/2];
Merge-Sort(A, p, q);
Merge-Sort(A, q, r);
Merge(A, p, q, r);
}
}

Megre(A, p, q, r)
{
n1 = q - p + 1;
n2 = r - q;
for (i = 0; i <= n1; i++)
L[i] = A [p+i];
for (j = 0; j <= n2; j++)
R[j] = A[q+j];
L[n1 +1] = Sentinel;
R[n2 +1] = Sentinel;
i = j = 0;
for (k = p; k <= r; k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
}
}

Features:
1. loop invariant
2. stable
3. T(n) = O(nlgn)

Insertion Sort

Input: A[1..N], length[A]

for (j=2; j <= length[A]; j++)
{
key = A[j];
i = j-1;
while (A[i] > key && i > 0)
{
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}

Features:
1. sort in place;
2. loop invariant;
3. stable sort;