4879

Сравнение эффективности алгоритмов сортировки

Лекция

Информатика, кибернетика и программирование

Сравнение эффективности алгоритмов сортировки. Каждый из рассмотренных алгоритмов сортировки обладает определенными преимуществами и недостатками. Для того, чтобы сравнивать между собой разные алгоритмы, необходимо сформулировать критерии, характери...

Русский

2012-11-28

47.5 KB

43 чел.

Сравнение эффективности алгоритмов сортировки.

Каждый из рассмотренных алгоритмов сортировки обладает определенными преимуществами и недостатками. Для того, чтобы сравнивать между собой разные алгоритмы, необходимо сформулировать критерии, характеризующие качество алгоритма. В качестве таких критериев могут выступать, например:

  •  скорость работы алгоритма, оцениваемая как суммарное необходимое количество «элементарных» операций. Часто в качестве такой элементарной операции выступает операция сравнения элементов последовательности. Заметим, что скорость работы может существенно зависеть от контекста, в котором выполняется алгоритм (аппаратное окружение, особенности входных данных и т.п.), в связи с чем может оказаться, что более важно оценивать, например, количество операций обмена элементов. Таким образом, выбор этого критерия определяется конкретными практическими соображениями, связанными с областью применения алгоритма. При этом часто важными являются оценки как в «предельных» случаях (т.е. в «лучшем» и «худшем»), так и «в среднем».
  •  необходимое количество памяти, требуемое для работы алгоритма. В этом смысле наиболее эффективны алгоритмы, не требующие выделения дополнительной памяти, такие алгоритмы часто называют сортировками на месте.
  •  зависимость от структуры исходных данных, например, поведение алгоритма для частично упорядоченных последовательностей, требование каких-либо особенностей входной последовательности и т.д.
  •  необходимость в рекурсивной реализации, может быть существенным фактором в условиях ограничений на доступную глубину стека вызовов.
  •  простота реализации, зачастую определяет выбор алгоритма в условиях ограниченного времени на разработку, отладку и тестирование алгоритма.

Оценки рассмотренных алгоритмов приведены в таблице:

Алгоритм

Вычислительная сложность

Требуемое количество памяти

В лучшем случае

В среднем

В худшем случае

«Пузырьковая» сортировка

O(N)

O(N2)

O(N2)

O(1)

Сортировка вставками

O(N)

O(N2)

O(N2)

O(1)

Сортировка выбором

O(N2)

O(N2)

O(N2)

O(1)

Сортировка Шелла

O(N)

O(N3/2)

O(N3/2)

O(1)

Быстрая сортировка

O(N logN)

O(N logN)

O(N2)

O(logN)

Пирамидальная сортировка

O(N logN)

O(N logN)

O(N logN)

O(1)

Сортировка слиянием

O(N logN)

O(N logN)

O(N logN)

O(N)

Для оценки фактического времени работы алгоритмов можно воспользоваться частью стандартной библиотеки (time.h), предоставляющей функции работы с системным таймером:

#include <iostream>

#include <time.h>

void main(int argc, char* argv[])

{

  // Синоним для типа данных "указатель на функцию"

  typedef void ( * t_SortFuncPrt )( double *, int );

  const int N_ALG = 7; // Число тестируемых алгоритмов

  // Массив указателей на все тестируемые функции сортировки

  t_SortFuncPrt sortAlgorithms[ N_ALG ] = { bubbleSort, insertSort, selectSort, shellSort, quickSort, heapSort, mergeSort };

  // Размер тестовой последовательности

  const int N = 10000;

  // Тестовые последовательности

  double * A[ N_ALG ];

  // Выделяем память

  for ( int i = 0; i < N_ALG; ++i )

     A[ i ] = new double[ N ];

  for ( int i = 0; i < N; ++i )

  {

     // Генерируем случайное число [0~1)

 double value = static_cast< double >( rand() ) / RAND_MAX;

     // Заполняем все тестовые последовательности одинаково

     for ( int j = 0; j < N_ALG; j++ )

        A[j][i] = value;

  }

 

  // Для каждого алгоритма

  for ( int i = 0; i < N_ALG; i++ )

  {

     // Засекаем текущее время

     clock_t before = clock();

     // Запускаем алгоритм

     sortAlgorithms[i]( A[i], N );

     // Засекаем время

     clock_t after = clock();

     // Общее время работы (мсек)

     clock_t totalTime = after - before;

     cout << "Algorithm " << i << ": " << totalTime << endl;

  }

  // Освобождаем память

  for ( int i = 0; i < N_ALG; ++i )

     delete[] A[ i ];

}


 

А также другие работы, которые могут Вас заинтересовать

25939. Выключатели нагрузки. Назначение, конструктивное исполнение и принцип действия выключателей нагрузки. Условия выбора 21 KB
  Выключатели нагрузки. Назначение конструктивное исполнение и принцип действия выключателей нагрузки. Выключатели нагрузки используются для оперативного соединения и разъединения цепи. Выключатель нагрузки обеспечивает двухкратное включение нормированного для него тока включения на короткое замыкание без повреждений препятствующих его дальнейшей работе в нормальном и эксплуатационном режиме.
25940. Расчет деревянных, металлических, железобетонных перекрытий 1.07 MB
  Орел 2011 Расчет деревянного перекрытия Подобрать сечение деревянной балки для перекрытия жилого дома.Предварительно принимаем собственный вес одного метра балки qnбалки=025кН м;f=1.1 qбалки= qnбалки f=0.Собираем нагрузку на погонный метр балки с учетом её собственного веса: qn=qnперекрытияlгр qnбалки=18140275=277кН м; q= qперекрытияlгр qбалки=234120275=3083кН м.
25941. СБОРНО-МОНОЛИТНЫЕ КОНСТРУКЦИИ 26.5 KB
  СБОРНОМОНОЛИТНЫЕ КОНСТРУКЦИИ конструкции состоящие из заранее изготовленных на заводах отд. Наибольшее распространение получили сборномонолитные конструкции со сборными элементами из железобетона см. Железобетонные конструкции . арматуру конструкции и иногда используются в качестве формы опалубки для монолитного бетона; их целесообразно делать предвари тсльно напряженными.
25942. Здания и сооружения из монолитного железобетона 31 KB
  Монолитные конструкции несущего остова здания представляют собой неразрезные элементы наружных и внутренних несущих стен колонн ригелей и перекрытий жестко связанных между собой в пространственную систему работающую под нагрузкой как единое целое. Здания из монолитного железобетона разделяются на монолитные и сборномонолитные и выполняются по следующим конструктивным схемам: монолитные несущие и ограждающие конструкции; монолитный каркас колонны и перекрытия наружные и внутренние стены сборные или каменных материалов; монолитные...
25943. Больше пролетные покрытия – плоскостные покрытия 68.5 KB
  Плоскостными покрытиями называют конструкции работающие только в одной вертикальной плоскости проходящей через опоры; к ним относятся балки фермы рамы арки; к ним следует отнести и те конструкции которые можно разрезать вертикальными плоскостями вдоль пролета на отдельные элементы причем каждый элемент независимо от другого будет тоже работать как плоскостной. К распорным плоскостным покрытиям относят своды арки рамы.
25944. Большепролетные покрытия - пространственные конструкции 561 KB
  Большепролетные покрытия пространственные конструкции. Все конструктивные системы покрытия можно рассматривать с двух позиций которые имеют особое влияние на архитектурный облик всего сооружения. В отличие от плоскостных пространственные покрытия работают одновременно в двух или нескольких направлениях К ним относятся: перекрестные системы оболочки складки висячие покрытия пневматические конструкции и др. Пространственные покрытия выполняют из плоскостных элементов монолитно связанных между собой и работающих как цельная конструкция...
25945. Большепролетные покрытия – висячие конструкции 67.5 KB
  Большепролетные покрытия висячие конструкции. Висячие конструкции представляют собой один из наиболее экономичных видов покрытий благодаря тому что материал несущих конструкций работает исключительно на растяжение и несущая способность конструкций используется полностью. б ужесточенными считают такие висячие системы жесткость которых препятствует возникновению недопустимых кинематических и упругих деформаций Сюда относятся в основном висячие предварительно напряженные оболочки.
25947. Большое распространение в зарубежной и отечественной практике получили также висячие тонколистовые системы - мембранные покрытия 76.5 KB
  В некоторых случаях вместо сплошной мембраны покрытие образуется из отдельных не соединяемых друг с другом тонких стальных лент. Сплошное мембранное покрытие успешно применено для универсального стадиона на проспекте Мира в Москве размеры в плане которого достигают 183x224 м рис.