БлогNot. Строим зависимость количества шагов сортировки от размерности массива

Строим зависимость количества шагов сортировки от размерности массива

Сортировки - одна из самых классических задач, имеющих широчайшую сферу применения.

Давайте сравним пару распространённых алгоритмов сортировки не по времени выполнения, как в этом скрипте на PHP, а по количеству шагов цикла, выполняемому алгоритмом. Фактически, это будет прямо коррелировать с временной сложностью.

Возьмём один из "базовых" алгоритмов (подойдут линейная сортировка выбором или сортировка "пузырьком", имеющие одинаковую вычислительную сложность) и один из "продвинутых", скажем, популярную быструю сортировку.

Меняя размерность массива от 100 до 10000, будем генерировать вектор случайных целочисленных значений, снимать с него копию и выполнять сортировки. Ниже показана программа на C++, проверенная в консоли Visual Studio 2019.

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct RandomGenerator { //функтор для генерации случайных чисел
 int maxValue;
 RandomGenerator(int max) : maxValue(max) {}
 int operator()() { return rand() % maxValue; }
};

template <class T> int linear (vector <T> &a) { //Линейная (отбором)
 T v;
 int n = a.size(),s=0,i,j;
 for (i = 0; i < n - 1; i++)
  for (j = i + 1; j < n; j++) {
   s++;
   if (a[i] > a[j]) { v=a[i]; a[i] = a[j]; a[j] = v; }
  }
 return s;
}

template <class T> int bubble (vector <T> &a) { 
 //Метод пузырька, то же количество шагов, что у linear, можно использовать вместо неё
 T v;
 int n = a.size(), s = 0, i, j;
 for (i = 1; i < n; i++)
  for (j = n - 1; j >= i; j--) {
   s++;
   if (a[j-1] > a[j]) { v = a[j-1]; a[j-1] = a[j]; a[j] = v; }
  }
 return s;
}

template <class T> int partition (vector <T> &a, int left, int right, int &s) { 
 //Выбор номера элемента для quick
 int val = a[left + (right - left) / 2];
 int i = left, j = right;
 T temp;
 while (i <= j) {
  while (a[i] < val) { i++; s++; }
  while (a[j] > val) { j--; s++; }
  s++;
  if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; }
 }
 return i;
}

template <class T> int quick (vector <T> &a, int left, int right, int &s) { 
 //Быстрая (с разделением)
 if (left < right) {
  int baseIndex = partition(a, left, right, s);
  quick(a, left, baseIndex - 1, s);
  quick(a, baseIndex, right, s);
 }
 return s;
}

template <class T> void print(string hdr, vector <T> &arr) {
 cout << hdr << ": ";
 for (T val : arr) cout << val << " "; 
 cout << endl;
}

int main() {
 const int size = 10000; //максимальная размерность теста, кратна 100
 for (int n = 100; n<=size; n+=100) {
  vector <int> arr1(n), arr2(n);
  generate (arr1.begin(), arr1.end(), RandomGenerator(n)); //сгенерировать случайный вектор
  //print ("arr1",arr1);
  double s1 = 0, s2 = 0; 
   //среднее количество шагов цикла сортировки за steps попыток
  int c;
  
  const int steps = 10;
  for (int i = 0; i < steps; i++) {
   random_shuffle(arr1.begin(), arr1.end()); //перемешать
   copy (arr1.begin(), arr1.end(), arr2.begin()); //сделать копию элементов
   s1 += linear (arr1); 
   //print ("arr1",arr1);
   c = 0;
   s2 += quick (arr2,0,n-1,c);
   //print ("arr2", arr2);
  }
  
  cout.precision(2);
  cout << setw(15) << fixed << (n) <<
          setw(15) << fixed << (s1 / steps) <<
          setw(15) << fixed << (s2 / steps) << endl;
 }

 cin.get(); return 0;
}

Полученные результаты и графики есть в приложенном документе Excel (2007 и выше). Видно, что у QuickSort количество операций растёт линейно в зависимости от размерности массива.

 Количество шагов цикла при линейной и быстрой сортировке для размерностей вектора от 100 до 10000, документ .xlsx в архиве .zip (20 Кб)

Следует иметь в виду, что контейнеры STL (как, впрочем, и строки std::string) имеют свойство сами "баловаться" с оперативкой, плюс контейнеры в любом случае выделяют память, необходимую для хранения объектов, в "куче" (динамически распредялемой области памяти), поэтому vector <T> *myvec = new vector <T> () вместо vector <T> myvec смысла не имеет.

Ну и вообще любое массовое динамическое выделение памяти существенно замедляет выполнение программы, особенно неявное выделение памяти через new :)


теги: тест числа алгоритм c++

15.02.2020, 15:11; рейтинг: 209