Chapter 10. Simple sorts

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// Selection sort algorithm

#include <iostream>
using namespace std;

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 selectionSort(Type a[], int n) {
  int i, j, min;
  for (i=0; i<n-1; i++) {
    min = i;
    for(j = i+1; j<n; j++)
      if(a[j] < a[min]) min = j;
    swap(a, i, min);
  }
}

int main() {
  int a[8] = { 77, 33, 44, 11, 88, 22, 66, 55}, i;
  char s[15] = {'a','s','o','r','t','i','n',
                'g','e','x','a','m','p','l','e'};

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

  for (i=0; i<8; i++) cout << a[i] << " ";
  cout << endl;
  for (i=0; i<15; i++) cout << s[i];
  cout << endl;
  
  selectionSort(a, 8);
  selectionSort(s, 15);

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

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

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// Insertion sort algorithm

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

template<class Type>
void insertionSort (Type a[], int n) {
  for(int i = 1; i < n; i++) {
    Type element = a[i];
    int j = i - 1;
    while ((j >= 0) && (element < a[j])) {
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = element;
  }
}

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

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

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

  insertionSort (a, 20);
  for (i = 0; i < 20; i++)
    cout << a[i] << ' ';
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// Bubble sort algorithm

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

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 bubbleSort (Type a[], int n) {
  for (int i = n - 1; i > 0; i--) 
    for (int j = 0; j < i; j++) 
      if (a[j] > a[j+1]) swap(a, j, j+1);
}

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

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

  for (i = 0; i < 20; i++) {
    a[i] = rand()%100;
    cout << a[i] << ' ';
  }

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

  bubbleSort(a, 20);
  for (i = 0; i < 20; i++)
    cout << a[i] << ' ';

  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// Bubble sort algorithm

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

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 bubbleSort (Type a[], int n) {
  bool sorted = false;
  for (int i=n-1; i>0 && !sorted; i--) {
    sorted = true;
    for (int j=0; j<i; j++) 
      if (a[j] > a[j+1]) {
        swap(a, j, j+1);
        sorted = false;
      }
  }
}


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

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

  for (i = 0; i < 20; i++) {
    a[i] = rand()%100;
    cout << a[i] << ' ';
  }

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

  bubbleSort(a, 20);

  for (i = 0; i < 20; i++)
    cout << a[i] << ' ';
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// Sort algorithm using "index array"


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

template<class Type>
void sort(Type a[], int p[], int n) {
  int i, j, k; Type t;
  for(i=0; i<n; i++) 
    if(p[i] != i) {
      t = a[i]; k = i;
      do {
        j = k; 
        a[j] = a[p[j]];
        k = p[j]; 
        p[j] = j;
      } while(k != i);
      a[j] = t;
    }
}

// using insertion sort

template<class Type>
void indexSort (Type a[], int p[], int n) {
  int i, j; Type t;
  for(i=0; i<n; i++) p[i] = i;
  for(i=1; i<n; i++) {
    t = p[i]; j = i - 1;
    while (j >= 0 && a[t] < a[p[j]]) {
      p[j+1] = p[j];
      j--;
    }
    p[j+1] = t;
  }
}


// using selection sort
/*
inline void swap(int p[], int i, int j) {
  int temp = p[i]; p[i] = p[j]; p[j] = temp;
}
template<class Type> void indexSort(Type a[], int p[], int n) {
  int i, j, min, t;
  for(i=0; i<n; i++) p[i] = i;
  for(i=0; i<n-1; i++) {
    min = i;
    for(j = i+1; j<n; j++)
      if(a[p[j]] < a[p[min]]) min = j;
        swap(p, i, min);
  }
}
*/


int main () {
  int a[20], index[20], i;

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

  for (i = 0; i < 20; i++) {
    a[i] = rand()%100;
    cout << a[i] << ' ';
  }

  indexSort (a, index, 20);
  cout << endl << "After Index sort:" << endl;
  
  for (i = 0; i < 20; i++)
    cout << a[index[i]] << ' ';
  cout << endl;

  sort(a, index, 20);

  for (i = 0; i < 20; i++)
    cout << a[i] << ' ';
  cout << endl;
  
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// Shell sort algorithm


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

template<class Type>
void shellSort (Type a[], int n) {
  int i, j, h; Type t;
  for(h=1; h<=n/9; h=h*3+1);
  for( ; h>0; h/=3)
    for(i=h; i<n; i++) {
      t = a[i]; j = i;
      while (j >=h && t < a[j-h]) {
        a[j] = a[j-h]; 
        j -=h;
      }
      a[j] = t;
    }
}


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

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

  for (i = 0; i < 20; i++) {
    a[i] = rand()%100;
    cout << a[i] << ' ';
  }

  shellSort (a, 20);

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

  for (i = 0; i < 20; i++)
    cout << a[i] << ' ';
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// Distribution counting sort algorithm

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

#define N 20
#define M 6 // keys' value between 0 and (M-1)

template<class Type>
void distributionCount(Type a[]) {
  int i, count[M]; 
  Type b[N];
  for(i=0; i<M; i++) count[i] = 0;
  for(i=0; i<N; i++) count[a[i]]++;
  for(i=1; i<M; i++) count[i] += count[i-1];
  for(i=N-1; i>=0; i--) b[--count[a[i]]] = a[i];
  for(i=0; i<N; i++) a[i] = b[i];
}

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

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

  for (i = 0; i < N; i++) {
    a[i] = rand()%M; // random value between 0 and M-1
    cout << a[i] << " ";
  }
  cout << endl;

  distributionCount(a);

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

  for (i = 0; i < N; i++)
    cout << a[i] << ' ';
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// Bucket sort algorithm

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

#define N 20
#define M 6 // keys' value between 0 and (M-1)

void bucketSort(unsigned int a[]) {
  int j, i, count[M]; 
  for(i=0; i<M; i++) count[i] = 0;
  for(i=0; i<N; i++) ++count[a[i]];
  for(j=0, i=0; i<M; i++)
    for( ; count[i]>0; --count[i])
      a[j++] = i;
}

int main () {
  unsigned int a[N], i;
  srand(time(0));

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

  for (i = 0; i < N; i++) {
    a[i] = rand()%M; // random value between 0 and M-1
    cout << a[i] << " ";
  }
  cout << endl;

  bucketSort(a);

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

  for (i = 0; i < N; i++)
    cout << a[i] << ' ';
  cout << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 10: Simple sorts

// List sort algorithm

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

typedef int Data;
class Node {
  Data element;
  Node *next;
  Node(const Data evalue, Node* nvalue = NULL) {
    element = evalue; next = nvalue; }
  friend class LinkedList;
};

class LinkedList {
  Node* head;
  Node* tail;
  Node* curr;
  void swap_value(Node*, Node*);
public:
  LinkedList() { head = tail = curr = NULL; }
  ~LinkedList(){};
  void insert(const Data);
  Data remove();
  void reset() { curr = NULL; }
  void next() { curr = curr->next; }
  void setFirst() { curr = head; }
  void setLast() { curr = tail; }
  void sort();
  void print();
  Node *getHead();
  void r_print(Node *);
};

void LinkedList::insert(const Data item){
  if(!curr) {
    head = curr = new Node(item, head);
    if(!tail) tail = head;
  }
  else {
    curr->next = new Node(item, curr->next);
    if(tail == curr) tail = curr->next;
  }
}

void LinkedList::print() {
  setFirst();
  while(curr) {
    cout << curr->element << " ";
    next();
  }
}

inline Node* LinkedList::getHead() { return head;}

void LinkedList::r_print(Node *p) {
  if(!p) return;
  else {
    r_print(p->next);
    cout << p->element << endl;
  }
}

inline void LinkedList::swap_value(Node *i, Node *j) {
  Data t = i->element;
  i->element = j->element;
  j->element = t; 
}

void LinkedList::sort() {
  Node *i, *j, *min;
  for(i = head; i != tail; i=i->next) {
    min = i;
    for(j=i->next; j; j=j->next)
      if(j->element < min->element) min = j;
    swap_value(i, min); 
  }
}

int main() {
  LinkedList list;
  srand(time(0));

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

  for(char i = 0; i < 10; i++) {
    list.setLast();
    list.insert(rand()%100);
  }

  list.print();
  cout << endl;

  list.sort();
  cout << endl << "After sort:" << endl;

  list.print();
  cout << endl;;

}