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

Писането на прости варианти на основни алгоритми
ни помага да ги разберем по-добре и след това да използваме
по-сложни варианти по-ефективно.
Робърт Седжуик
    Една от най-често срещаните задачи при обработка на големи еднотипни данни е сортирането - нареждане на данните "по големина". Такава подредба улеснява търсенето на определена данна в голям масив от данни (вж 17. Търсене, бързо сортиране).

  Сортиране чрез селекция (пряка селекция).
    Алгоритъмът се състои в следното: на всяка стъпка намираме най-малкия елемент (от ненаредената част на масива) и го поставяме на място (чрез размяна) в наредения масив.
Пример:

0.ст. 1.ст. 2.ст. 3.ст. 4.ст. 5.ст.
8 4* 4* 4* 4* 4*
7 7 5* 5* 5* 5*
5 5 7 7* 7* 7*
10 10 10 10 8* 8*
4 8 8 8 10 9*
9 9 9 9 9 10*
0 - елемент за размяна
0 - най-малък елемент
0* - елемент, който е вече е подреден

    Програмата ще реализираме със заглавни файлове и модули. Пряката селекция е в модула selsort (файлове selsort.h и selsort.cpp), функциите за генериране и отпечатване на вектор от цели чиса - в модула utilv (файлове utilv.h  и utilv.cpp) и главна функция main във файла sels_test.cpp.

// selsort.h
#ifndef SELSORT_H
#define SELSORT_H
#include <vector>
using namespace std;
void selection_sort(vector<int> &);
#endif

// selsort.cpp
#include <vector>
#include "selsort.h"
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;
  for (int 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]);
  }
}
// end selsort.cpp

// utilv.h
#ifndef UTILV_H
#define UTILV_H
#include <vector>
using namespace std;

void print(vector<int>);
void generate(vector<int> &);
#endif

// utilv.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include "utilv.h"
using namespace std;

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

void generate(vector<int> &a)
{ rand_seed();
  int i;
  for (i = 0; i < v.size(); i++) v[i] = rand_int(1, 100);
}
// end utilv.cpp

// sels_test.cpp
#include <iostream>
#include <vector>
#include "selsort.h"
#include "utilv.h"
using namespace std;

int main()
{ cout << "Enter vector size: ";
  int n;
  cin >> n;
  vector<int> v(n);
  generate(v);
  print(v);
  selection_sort(v);
  print(v);
  return 0;
}

Enter vector size: 10
92 11 61 53 25 18 100 8 17 79 
8 11 17 18 25 53 61 79 92 100 

Измерване на времето за работа на алгоритъма за сортиране чрез  селекция.
    Времето за работа на една програма можем да измерим като използваме класа Time, чийто конструктор без параметри конструира обект, съдържащ текущото време на компютъра.

// sorttime.cpp
#include <iostream>
#include <vector>
#include "selsort.h"
#include "utilv.h"
using namespace std;

#include "ccc_time.cpp"

int main()
{ cout << "Enter vector size: ";
  int n;
  cin >> n;
  vector<int> v(n);
  generate(v);

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

Enter vector size: 8000
Elapsed time = 54 seconds

    С няколко изпълнения на програмата получаваме следната таблица:

Vector size Elapsed time
1000 2
2000 4
4000 15
8000 54


Анализ на ефективността на алгоритъма за сортиране чрез  селекция.
    Ще преброим обръщенията към елементите на масив с n елементи. На първата стъпка правим n-1 сравнения за да намерим най-малкия елемент на масива - следователно точно n обръщения. После още 2 за (евентуална) размяна на елементите. На втората стъпка правим същото, но вече за масив с n-1 елемента, и т.н. Следователно общият брой обръщения е:
n + 2 + n - 1 + 2 + ... + 2 + 2 = n + (n-1) + (n-2) + ... + 2 + (n-1)2 =
n(n+1)/2 + 1 +2(n-1) = 0.5n2 + 2.5n - 3.
Казваме, че броят на обръщенията е от порядък на n2, което означава, че ако увеличим елементите на масива k пъти, броят на обръщенията ще се увеличи k2  пъти. Предполагаме, че този брой е пропорционален на времето за изпълнение на програмата. Следователно, ако програмата е работила 10 секунди за масив от 3000 елемента, то за масив от 30000 елемента ще работи 10х102 = 1000 секунди > 12 минути.
    Затова се казва, че сложността на алгоритъма за сортиране чрез селекция е от порядъка на n2 и се записва O(n2) - чете се о-голямо от n2.

Сортиране чрез сливане.
    Ако двете половини на вектор a са сортиране, то можем да слеем двете половинки в един сортиран вектор b.
 

Вектор a
Стъпка
2 1*
4 2 3*
8 4*
15 6 7 8*
19 10*
3 1 2*
9 3 4 5*
10 6*
11 7*
16 8 9*
Вектор b
1.ст. 2.ст. 3.ст. 4.ст. 5.ст. 6.ст. 7.ст. 8.ст. 9.ст. 10.ст.
2<3 4>3 4<9 8<9 15>9 15>10 15>11 15<16 19>16 19
2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
8 8 8 8 8 8 8
9 9 9 9 9 9
10 10 10 10 10
11 11 11 11
15 15 15
16 16
19
    Идеята на сортировката по този метод е рекурсивно извикване на функцията за сортиране за 2 пъти по-малко елементи до достигане на тривиалния случай - сортиране на един елемент.
// mergesort.cpp
#include <iostream>
#include <vector>
#include "utilv.h"
using namespace std;

void merge(vector<int> &a, int from, int mid, int to)
/* ЦЕЛ: слива две съседни части на вектор
   ПОЛУЧАВА: a - вектора, чиито елемент си сливат
             from, mid - начало и край на първата част
             to - край на втората част
*/
{ int n = to - from + 1; /* размер на частта, която се слива */
/* двете половинки се сливат във временен вектор b */
  vector<int> b(n);
  int i1 = from;
/* следващият елемент от първата половина */
  int i2 = mid + 1;
/* следващият елемент от втората половина */
  int j = 0; /* следваща свободна позиция в b */

/* докато нито i1 нито i2 са преминали края, копираме по-малкия елемент в b */
  while (i1 <= mid && i2 <= to)
  { if (a[i1] < a[i2]) { b[j] = a[i1];   i1++; }
    else               { b[j] = a[i2];   i2++; }
    j++;
  }
/* само един от двата цикъла ще се изпълни */
/* копиране на оставащите елементи от първата половина */
   while (i1 <= mid) { b[j] = a[i1];   i1++;   j++; }
/* копиране на оставащите елементи от втората половина */
   while (i2 <= to)  { b[j] = a[i2];   i2++;   j++;   }

/* копиране обратно от временния вектор */
  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;
/* сортиране на първата и втората половина */
  merge_sort(a, from, mid);
  merge_sort(a, mid+1, to);
  merge(a, from, mid, to);
}

int main()
{ vector<int> v(20);
  generate(v);
  print(v);
  merge_sort(v, 0, v.size()-1);
  print(v);
  return 0;
}

29 59 16 5 28 38 33 37 32 48 10 92 80 16 6 41 80 81 52 17 
5 6 10 16 16 17 28 29 32 33 37 38 41 48 52 59 80 80 81 92 

Анализ на алгоритъма за сортиране чрез сливане.
    На всяка стъпка от сливането правим сравнение между един елемент от първата половина на a и един елемент от втората половина на a и записваме един елемент в b, т.е. правим 3 обръщения към елементи на масивите. За обратното копиране на b в a имаме още 2 обръщения. Или общо 5n обръщения за вектор от n елемента. Нека T(n) е функцията, която задава броя на обръщенията. Тогава поради двете рекурсивни извиквания с два пъти по-малък вектор имаме:

T(n) = T(n/2) + T(n/2) + 5n.
За да изразим явно T(n) използваме равенствата:
                T(n) = 2T(n/2) + 5n = 4T(n/4) + 10n = 8T(n/8) + 15n = ... = 2kT(n/2k) + 5kn
и за n = 2k получаваме T(n) = nT(1) + 5n log2n, т.е. сложността на алгоритъма е O(n log n).
    Тъи като n log2n < n2  за n > 2, то алгоритъма за сортиране чрез сливане е по-добър (по-ефективен) от алгоритъма за сортиране чрез селекция. За сметка на това, този алгоритъм използва два пъти повече памет от пряката селекция.