Chapter 11. Advanced sorts

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms

// Quick sort algorithm
// using recursion

#include <iostream>
#include <ctime>
using namespace std;

template<class Type>
inline void swap(Type a[], int i, int j) {
  Type t = a[i]; a[i] = a[j]; a[j] = t;
}

template<class Type>
int partition(Type a[], int l, int r) {
  Type v = a[r];
  int i = l-1, j = r;
  for(;;) {
    while(a[++i] < v);
    while(j>l && a[--j] > v);
    if(i>=j) break;
    swap(a, i, j);
  } 
  swap(a, i, r);
  return i;
}

template<class Type>
void quickSort(Type a[], int l, int r) {
  if(l<r) {
    int i = partition(a, l, r);
    quickSort(a, l, i-1);
    quickSort(a, i+1, r);
  }
}

int main() {
  char a[15], i;
  srand(time(0));

  cout << "Before sort:" << endl;

  for(i=0; i<15; i++) {
    a[i] = 65 + rand()%24; 
    cout << a[i] << " ";
  }
  cout << endl;

  quickSort(a, 0, 14);

  cout << endl << "After sort:" << endl;

  for(i=0; i<15; i++)
    cout << a[i] << " ";
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms

// Radix sort algorithm

#include <iostream>
#include <ctime>
using namespace std;

class bitskey {
  int x;
public:
  bitskey& operator=(int i) {
    x = i; return *this; 
  }
  inline unsigned bits(int k, int j) {
    return (x >> k) & ~(~0 << j);
  }
  friend ostream& operator<<(ostream& out, bitskey& a) {
    out << a.x;
    return out;
  }
};

typedef bitskey itemType;

template<class Type>
inline void swap(Type a[], int i, int j) {
  Type temp = a[i]; a[i] = a[j]; a[j] = temp;
}

void radixSort(itemType a[], int l, int r, int b) {
  int i, j;
  if(r>l && b>=0) {
    i = l; j = r;
    while(j != i) {
      while(!a[i].bits(b,1) && i<j) i++;
      while( a[j].bits(b,1) && j>i) j--;
      swap(a,i,j);
    }
    if(!a[r].bits(b,1)) j++;
    radixSort(a, l, j-1, b-1);
    radixSort(a, j, r, b-1);
  }
}

int main() {
  int i, n = 10;
  itemType a[10];
  
  srand(time(0));

  cout << "Before sort:" << endl;

  for(i=0; i<n; i++) {
    a[i] = rand()%100;  // all elements less than 100
    cout << a[i] << " ";
  }
  cout << endl;

  radixSort(a, 0, n-1, 6); // 100 has 7 bits in binary
  cout << endl << "After sort:" << endl;

  for(i=0; i<n; i++) 
    cout << a[i] << " ";
    cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms
// Chapter 12: Simple search algorithms

// Binary Search Tree

#include <iostream>
#include <ctime>
using namespace std;

template <class Type>
class BSTree {
  struct Node {
    Type data;
    Node *l, *r;
    Node(Type d) : data(d), l(NULL), r(NULL) {}
  };    
  Node *root;
public:
  BSTree() { root = NULL; }
  Node *&getroot() { return root;}
  void insert(Type d);
  bool search(Node *tp, Type d);
  bool search(Type d);
  void inorder(Node *tp);
  void deleteItem(Node *&tp, Type d);
  void deleteNode(Node *&tp);
  Type processLeftMost(Node *&tp);
};

template <class Type>
void BSTree<Type>::insert(Type d) {
  Node *tp = root, *ptp;
  while(tp) {
    ptp = tp;
    tp = (d < tp->data) ? tp->l : tp->r;
  }
  tp = new Node(d);
  if(!root) root = tp;
  else {
    if(ptp->data > d) ptp->l = tp; 
    else ptp->r = tp;
  }
}

template <class Type>
void BSTree<Type>::inorder(Node *tp) {
  if(tp->l) inorder(tp->l);
  cout << tp->data << " ";
  if(tp->r) inorder(tp->r);

}

template <class Type>
bool BSTree<Type>::search(Type d){
  Node *tp = root;
  while(tp) {
    if(d == tp->data) return true;
    else if(d < tp->data) tp = tp->l;
    else tp = tp->r;
  }
  return false;
}

template <class Type>
bool BSTree<Type>::search(Node *tp, Type d) {
  if(!tp) return false;
  else if(d == tp->data) return true;
  else if(d < tp->data) return search(tp->l,d);
  else return search(tp->r,d);
}

template <class Type>
void BSTree<Type>::deleteItem(Node *&tp, Type d) {
  if (tp == NULL) { return; }
  else if(d == tp->data)  deleteNode(tp);
  else if(d < tp->data)	deleteItem(tp->l,d);
  else deleteItem(tp->r,d);
}

template <class Type>
void BSTree<Type>::deleteNode(Node *&tp) {  
  Node *tmp;
  
  // 1. tp is a leaf
  if((tp->l == NULL) && (tp->r == NULL)) {	
    delete tp;
    tp = NULL;
  }
  
  // 2. tp has only a left child
  else if((tp->l != NULL) && (tp->r == NULL)) {
    tmp = tp;
    tp = tp->l;
    delete tmp;
  }
  
  // 3. tp has only a right child
  else if((tp->l == NULL) && (tp->r != NULL)) {
    tmp = tp;
    tp = tp->r;
    delete tmp;
  }
  
  // 4. tpr has two children.
  else
    tp->data = processLeftMost(tp->r);
}

template <class Type>
Type BSTree<Type>::processLeftMost(Node *&tp) {  	
  Type d;
  Node* tmp;
  if(tp->l == NULL) {
    d = tp->data;
    tmp = tp;
    tp = tp->r;
    delete tmp;
    return d;
  }
  else 
    return processLeftMost(tp->l);
}

int main() {
  BSTree<int> tree;
  int i, k;
  srand(time(0));
  for(i=0; i<10; i++) {
    k = rand()%100;
    cout << k << " ";
    tree.insert(k);
  }
  cout << endl;
  tree.inorder(tree.getroot());
  cout << "\nSearch data: "; cin >> i; 
  if(tree.search(tree.getroot(),i)) cout << "found\n";
  else cout << "not found\n";
  cout << "Delete data:"; cin >> i;
  tree.deleteItem(tree.getroot(),i);
  tree.inorder(tree.getroot());
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms

// Binary Search Tree
// using friend class

#include <iostream>
#include <ctime>
using namespace std;

template <class Type>
class Node {
  template <class> friend class BSTree;
  Type data;
  Node *l, *r;
  Node(Type d) : data(d), l(NULL), r(NULL) {}
};    

template <class Type>
class BSTree {
  Node<Type> *root;
public:
  BSTree() { root = NULL; }
  Node<Type> *&getroot() { return root;}
  void insert(Type d);
  bool search(Node<Type> *tp, Type d);
  bool search(Type d);
  void inorder(Node<Type> *tp);
  void deleteItem(Node<Type> *&tp, Type d);
  void deleteNode(Node<Type> *&tp);
  Type processLeftMost(Node<Type> *&tp);
};

template <class Type>
void BSTree<Type>::insert(Type d) {
  Node<Type> *tp = root, *ptp;
  while(tp) {
    ptp = tp;
    tp = (d < tp->data) ? tp->l : tp->r;
  }
  tp = new Node<Type>(d);
  if(!root) root = tp;
  else {
    if(ptp->data > d) ptp->l = tp; 
    else ptp->r = tp;
  }
}

template <class Type>
void BSTree<Type>::inorder(Node<Type> *tp) {
  if(tp->l) inorder(tp->l);
  cout << tp->data << " ";
  if(tp->r) inorder(tp->r);

}

template <class Type>
bool BSTree<Type>::search(Type d){
  Node<Type> *tp = root;
  while(tp) {
    if(d == tp->data) return true;
    else if(d < tp->data) tp = tp->l;
    else tp = tp->r;
  }
  return false;
}

template <class Type>
bool BSTree<Type>::search(Node<Type> *tp, Type d) {
  if(!tp) return false;
  else if(d == tp->data) return true;
  else if(d < tp->data) return search(tp->l,d);
  else return search(tp->r,d);
}

template <class Type>
void BSTree<Type>::deleteItem(Node<Type> *&tp, Type d) {
  if (tp == NULL) { return; }
  else if(d == tp->data)  deleteNode(tp);
  else if(d < tp->data)	deleteItem(tp->l,d);
  else deleteItem(tp->r,d);
}

template <class Type>
void BSTree<Type>::deleteNode(Node<Type> *&tp) {  
  Node<Type> *tmp;
  
  // 1. tp is a leaf
  if((tp->l == NULL) && (tp->r == NULL)) {	
    delete tp;
    tp = NULL;
  }
  
  // 2. tp has only a left child
  else if((tp->l != NULL) && (tp->r == NULL)) {
    tmp = tp;
    tp = tp->l;
    delete tmp;
  }
  
  // 3. tp has only a right child
  else if((tp->l == NULL) && (tp->r != NULL)) {
    tmp = tp;
    tp = tp->r;
    delete tmp;
  }
  
  // 4. tpr has two children.
  else
    tp->data = processLeftMost(tp->r);
}

template <class Type>
Type BSTree<Type>::processLeftMost(Node<Type> *&tp) {  	
  Type d;
  Node<Type>* tmp;
  if(tp->l == NULL) {
    d = tp->data;
    tmp = tp;
    tp = tp->r;
    delete tmp;
    return d;
  }
  else 
    return processLeftMost(tp->l);
}

int main() {
  BSTree<int> tree;
  int i, k;
  //  srand(time(0));
  for(i=0; i<10; i++) {
    k = rand()%100;
    cout << k << " ";
    tree.insert(k);
  }
  cout << endl;
  tree.inorder(tree.getroot());
  cout << "\nSearch data: "; cin >> i; 
  if(tree.search(tree.getroot(),i)) cout << "found\n";
  else cout << "not found\n";
  cout << "Delete data:"; cin >> i;
  tree.deleteItem(tree.getroot(),i);
  tree.inorder(tree.getroot());
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms

// Sort algorithm using Binary Search Tree

#include <iostream>
#include <ctime>
using namespace std;


template <class Type>
class BSTree {
  struct Node {
    Type data;
    Node *l, *r;
    Node(Type d) : data(d), l(NULL), r(NULL) {}
  };    
  Node *root;
public:
  BSTree() { root = NULL; }
  Node *&getroot() { return root;}
  void insert(Type d);
  void inorder(Node *tp, Type a[]);
};

template <class Type>
void BSTree<Type>::insert(Type d) {
  Node *tp = root, *ptp;
  while(tp) {
    ptp = tp;
    tp = (d<tp->data) ? tp->l : tp->r;
  }
  tp = new Node(d);
  if(!root) root = tp;
  else {
    if(ptp->data>d) ptp->l = tp; 
    else ptp->r = tp;
  }
}

template <class Type>
void BSTree<Type>::inorder(Node *tp, Type a[]) {
  static int i=0;
  if(tp->l) inorder(tp->l, a);
  a[i++] = tp->data;
  if(tp->r) inorder(tp->r, a);
}

template <class Type>
void treeSort(Type a[], int n) {
  BSTree<int> tree;
  int i;
  for(i=0; i<n; i++)
    tree.insert(a[i]);
  tree.inorder(tree.getroot(), a);  
}

int main() {
  int i , a[10], n = 10;

  srand(time(0));
  cout << "Before sort:" << endl;

  for(i=0; i<n; i++) {
    a[i] = rand()%100;
    cout << a[i] << " ";
  }
  cout << endl;

  treeSort(a,n);
  cout << endl << "After sort:" << endl;

  for(i=0; i<n; i++) 
    cout << a[i] << " ";
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms

// Sort algorithm using Binary Search Tree
// using friend class

#include <iostream>
#include <ctime>
using namespace std;

template <class Type>
class Node {
  template <class> friend class BSTree;
  Type data;
  Node *l, *r;
  Node(Type d) : data(d), l(NULL), r(NULL) {}
};    


template <class Type>
class BSTree {
  Node<Type> *root;
public:
  BSTree() { root = NULL; }
  Node<Type> *&getroot() { return root;}
  void insert(Type d);
  void inorder(Node<Type> *tp, Type a[]);
};

template <class Type>
void BSTree<Type>::insert(Type d) {
  Node<Type> *tp = root, *ptp;
  while(tp) {
    ptp = tp;
    tp = (d<tp->data) ? tp->l : tp->r;
  }
  tp = new Node<Type>(d);
  if(!root) root = tp;
  else {
    if(ptp->data>d) ptp->l = tp; 
    else ptp->r = tp;
  }
}

template <class Type>
void BSTree<Type>::inorder(Node<Type> *tp, Type a[]) {
  static int i=0;
  if(tp->l) inorder(tp->l, a);
  a[i++] = tp->data;
  if(tp->r) inorder(tp->r, a);
}

template <class Type>
void treeSort(Type a[], int n) {
  BSTree<int> tree;
  int i;
  for(i=0; i<n; i++)
    tree.insert(a[i]);
  tree.inorder(tree.getroot(), a);  
}

int main() {
  int i , a[10], n = 10;

  srand(time(0));
  cout << "Before sort:" << endl;
  for(i=0; i<n; i++) {
    a[i] = rand()%100;
    cout << a[i] << " ";
  }
  cout << endl;

  treeSort(a,n);

  cout << endl << "After sort:" << endl;
  for(i=0; i<n; i++) 
    cout << a[i] << " ";
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms

// Heap sort algorithm

#include <iostream>
#include <ctime>
using namespace std;

template <class Type>
class Heap {
  Type *array;
  int MaxSize, Nel;
  void adjustH(int k);
public:
  Heap(int MSize) : MaxSize(MSize) {
    array = new Type[MaxSize+1]; Nel = 0;
  }
  ~Heap() { delete []array; }
  bool insert(Type item);
  bool rmmax(Type& item);
  void print();
};

template <class Type> 
bool Heap<Type>::insert(Type item) {
  int i ;
  if(Nel==MaxSize) {
    cout << "Heap size exceeded!" << endl;
    return false;
  }
  i = ++Nel;
  while((i>1) && (array[i/2]<item)) {
    array[i] = array[i/2]; i /= 2;
  }
  array[i] = item;
  return true;
}

template <class Type>
void Heap<Type>::adjustH(int k) {
  int j = 2*k;
  Type item = array[k];
  while(j<=Nel) {
    if((j<Nel) && (array[j] < array[j+1])) j++;
    if(item>=array[j]) break;
    array[j/2] = array[j]; j *= 2;
  }
  array[j/2] = item;
}

template <class Type>
bool Heap<Type>::rmmax(Type& item) {
  if(!Nel) {
    cout << "Heap is empty!" << endl;
    return false;
  }
  item = array[1]; array[1] = array[Nel--];
  adjustH(1);
  return true;
}

template <class Type>
void Heap<Type>::print() {
  int i;
  for(i=1; i<=MaxSize; i++)
    cout << array[i]<< " ";
  cout << endl;
}

template<class Type>
void heapSort(Type a[], const int n) {
  Heap<Type> heap(n);
  int i;
  for(i=0; i<n; i++)
    heap.insert(a[i]);
  heap.print();
  for(i=n-1; i>=0; i--) 
    heap.rmmax(a[i]);
}


int main() {
  const int n=20;
  int a[n], i;
  srand(time(0));
  cout <<"before sort:\n";
  for(i=0; i<n; i++) {
    a[i] = rand()%100;
    cout << a[i] << " ";
  }
  cout << "\nHeap:" << endl;
  
  heapSort(a, n);
  cout << "after sort:\n";
  for(i=0; i<n; i++)
    cout << a[i] << " ";
  cout << endl; 
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms

// Heap sort algorithm
// without Heap class

#include <iostream>
#include <ctime>
using namespace std;

template <class Type>
void adjustH(Type array[], int k, int Nel) {
  int j = 2*k;
  Type item = array[k];
  while(j<=Nel) {
    if((j<Nel) && (array[j] < array[j+1])) j++;
    if(item>=array[j]) break;
    array[j/2] = array[j]; j *= 2;
  }
  array[j/2] = item;
}

template<class Type>
inline void swap(Type a[], int i, int j) {
  Type temp = a[i]; a[i] = a[j]; a[j] = temp;
}

template<class Type>
void heapSort(Type a[], const int n) {
  // a[1:n] contain n elements to be sorted.
  int i;
  for(i=n/2; i; i--) 
    adjustH(a, i, n);
  for(i=n; i>=2; i--) {
    swap(a, 1, i);
    adjustH(a, 1, i-1);
  }
}

int main() {
  int n=20;
  int i, a[21];
  srand(time(0));
  cout <<"before sort:\n";
  for(i=1; i<=n; i++) {
    a[i] = rand()%100;
    cout << a[i] << " ";
  }
  
  heapSort(a, n);

  cout << "\nafter sort:\n";
  for(i=1; i<=n; i++)
    cout << a[i] << " ";
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 11: Advanced sorting algorithms

// Merge sort algorithm

#include <iostream>
#include <ctime>
using namespace std;

template <class Type>
void merge(Type a[], Type tmp[], int low, int mid, int high) {
  int i, j, k;
  for (i=mid+1; i>low; i--) tmp[i-1] = a[i-1];
  for (j=mid; j<high; j++) tmp[high+mid-j] = a[j+1];
  for (k=low; k<=high; k++)
    a[k] = (tmp[i] < tmp[j]) ? tmp[i++] : tmp[j--];
}

template <class Type>
void divconMerge(Type a[], Type tmp[], int high, int low = 0) {
  if (low < high) { 
    int mid = (low + high)/2;
    divconMerge(a, tmp,  mid, low);
    divconMerge(a, tmp, high, mid + 1);
    merge(a, tmp, low, mid, high);
  }
}

template <class Type>
void mergeSort(Type a[], int n) {
  Type *tmp = new Type[n];
  divconMerge(a, tmp, n-1);
  delete []tmp;
}

int main() {
  int i, n = 10;
  int a[10];

  srand(time(0));
  cout << "Before sort:" << endl;

  for(i=0; i<n; i++) {
    a[i] = rand()%100;
    cout << a[i] << " ";
  }
  cout << endl;

  mergeSort(a, n);
  cout << endl << "After sort:" << endl;

  for(i=0; i<n; i++) 
    cout << a[i] << " ";
  cout << endl;
}