Бүлэг 10. Эрэмбэлэлтийн энгийн аргууд

Агуулга: Энэ бүлэгт ашигласан программын кодуудыг энд үзүүллээ. Эрэмбэлэлтийн алгорирмуудыг судлах энэ хэсэгт бид эрэмбэлэлтийн энгийн аргуудтай танилцах юм. Эрэмбэлэлт хийхэд энгийн аргуудыг сонгох зарим хэрэглээ ба шаардлага байдаг.

Сонгон эрэмбэлэх арга

// 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;
}

Бөмбөлгөн эрэмбэлэлтийн арга

хувилбар - I

// 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;
}

хувилбар - II

// 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;
  
}

Shell-ийн арга

// 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;;

}