6. Прости алгоритми за сортиране

  Сортиране чрез селекция
 Намираме най-малкия елемент и го поставяме на място.
// selsort.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

void swap(int& x, int& y)
{  int temp = x;   x = y;   y = temp;  }

int min_position(vector<int>& a, int from, int to)
{
   int min_pos = from;
   int i;
   for (i = from + 1; i <= to; i++)
       if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}

void selection_sort(vector<int>& a)
{
   int next; /* the next position to be set to the minimum */

   for (next = 0; next < a.size() - 1; next++)
   {  /* find the position of the minimum */
      int min_pos = min_position(a, next, a.size() - 1);
      if (min_pos != next)
         swap(a[min_pos], a[next]);
   }
}

void print(vector<int> a)
{
   int i;
   for (i = 0; i < a.size(); i++) cout << a[i] << " ";
   cout << "\n";
}

void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}

int rand_int(int a, int b)
{  return a + rand() % (b - a + 1); }

int main()
{
   rand_seed();
   vector<int> v(20);
   int i;
   for (i = 0; i < v.size(); i++)
   v[i] = rand_int(1, 100);
   print(v);
   selection_sort(v);
   print(v);
   return 0;
}

Измерване на времето за работа и анализ на  ефективността на алгоритъма за сортиране чрез  селекция

// sorttime.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

#include "ccc_time.cpp"

void swap(int& x, int& y)
{  int temp = x;   x = y;   y = temp;  }

int min_position(vector<int>& a, int from, int to)
{
   int min_pos = from;
   int i;
   for (i = from + 1; i <= to; i++)
       if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}

void selection_sort(vector<int>& a)
{
   int next;
   for (next = 0; next < a.size() - 1; next++)
   {
      int min_pos = min_position(a, next, a.size() - 1);
      if (min_pos != next)  swap(a[min_pos], a[next]);
   }
}

void rand_seed()
/* PURPOSE: Set the seed of the random number generator
*/
{  int seed = static_cast<int>(time(0));
   srand(seed);
}

int rand_int(int a, int b)
{  return a + rand() % (b - a + 1);  }

int main()
{
   rand_seed();
   cout << "Enter vector size: ";
   int n;
   cin >> n;
   vector<int> v(n);
   int i;
   for (i = 0; i < v.size(); i++) v[i] = rand_int(1, 100);
   Time before;
   selection_sort(v);
   Time after;

   cout << "Elapsed time = " << after.seconds_from(before)
        << " seconds\n";
   return 0;
}

Сортиране чрез сливане
// mergesort.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

void merge(vector<int>& a, int from, int mid, int to)
{
   int n = to - from + 1; /* size of the range to be merged */
/* merge both halves into a temporary vector b */
   vector<int> b(n);

   int i1 = from;
/* next element to consider in the first half */
   int i2 = mid + 1;
/* next element to consider in the second half */
   int j = 0; /* next open position in b */

/* as long as neither i1 nor i2 past the end, move the smaller      element into b */
   while (i1 <= mid && i2 <= to)
   {  if (a[i1] < a[i2])    {  b[j] = a[i1];   i1++;   }
      else                  {  b[j] = a[i2];   i2++;   }
      j++;
   }
/* note that only one of the two while loops below is executed */

/* copy any remaining entries of the first half */
   while (i1 <= mid)   {  b[j] = a[i1];      i1++;      j++;   }

/* copy any remaining entries of the second half */
   while (i2 <= to)   {  b[j] = a[i2];      i2++;      j++;   }

/* copy back from the temporary vector */
   for (j = 0; j < n; j++)   a[from + j] = b[j];
}

void merge_sort(vector<int>& a, int from, int to)
{
   if (from == to) return;
   int mid = (from + to) / 2;
/* sort the first and the second half */
   merge_sort(a, from, mid);
   merge_sort(a, mid + 1, to);
   merge(a, from, mid, to);
}

void print(vector<int> a)
{
   int i;
   for (i = 0; i < a.size(); i++)  cout << a[i] << " ";
   cout << "\n";
}

void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}

int rand_int(int a, int b)
{  return a + rand() % (b - a + 1);   }

int main()
{
   rand_seed();
   vector<int> v(20);
   int i;
   for (i = 0; i < v.size(); i++)
      v[i] = rand_int(1, 100);
   print(v);
   merge_sort(v, 0, v.size() - 1);
   print(v);
   return 0;
}

Анализ на алгоритъма за сортиране чрез сливане