4879

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

Лекция

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

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

Русский

2012-11-28

47.5 KB

36 чел.

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

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

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

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

Алгоритм

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

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

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

В среднем

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

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

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

}


 

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

37660. Тепловой расчет блока 137.5 KB
  Вычисляем приведенную высоту деталей размещенных на кассете: 2. Вычисляем поверхность рабочей зоны охватывающей четыре кассеты 5. Вычисляем площадь поверхности кассет обращенных друг к другу: 6. Вычисляем значение коэффициента 9.
37661. Расчет транзисторного ключа 157.5 KB
  Задержка включения как указывалось обусловлена наличием входной емкости Свх транзистора.1б: где – постоянная времени входной цепи транзистора; – сопротивление резистора в этой цепи.1в имеет Исходные данные: питание коллектора Ек = 13В; сопротивление коллектора Rк = 17кОм; сопротивление базы Rб = 23 кОм; напряжение В; постоянная времени транзистора в схеме с общим эмиттером коэффициент усиления транзистора емкость коллектора Ск = 5пФ; емкость эмиттера Сэ = 5пФ; напряжение порога переключения транзистора Требуется...
37662. Расчет надежности двухканального усилителя 421.5 KB
  Обеспечение надежности является одной из основных задач техники. Надежностью называют свойство изделия выполнять заданные функции, сохраняя во времени значения установленных эксплуатационных показателей в заданных пределах, соответствующих заданным режимам и условиям использования, технического обслуживания, хранения и транспортирования.
37663. Расчет транзисторного мультивибратора в автоколебательном режиме 161 KB
  Мультивибраторами называют электронные устройства, генерирующие электрические колебания, близкие по форме к прямоугольной. Спектр колебаний, генерируемых мультивибратором, содержит множество гармоник - тоже электрических колебаний, но кратных колебаниям основной частоты, что и отражено в его названии: мульти - много, вибро - колеблю.
37664. Анализ и расчет технологичности двухканального усилителя 664.5 KB
  Практическая работа №03 Анализ и расчет технологичности двухканального усилителя Под технологичностью изделия понимается определённое количество параметров выпускаемого на производстве изделия технологической подготовки и производственного процесса от которых в результате зависит качество изделия. Комплексный показатель технологичности рассчитывается с использованием базовых показателей по следующей формуле: где: Кi базовый показатель технологичности; φi коэффициент характеризующий весовую значимость базового показателя технологичности;...
37666. Файли. Обробка файлів 449.25 KB
  Організувати послідовний файл на диску. Блок організації файла оформити окремою процедурою. Роботу бази організувати в діалоговому режимі. Окремими процедурами здійснити: редагування вибраного запису, тобто зміни запису за вибором; пошук за індексом запису в базі даних і виведення інформації про його наявність;
37668. Проектирование архитектуры ПО 54 KB
  Киев 2010 Проектирование архитектуры ПО Цель: исследование диаграмм компонентов и развертывание обретение навыков в их использовании. Диаграмма компонентов Архитектура ПО это представление ПО с помощью базовых элементов трех типов: компонентов соединителей и данных. Диаграмма компонентов Component digrm описывает физическое представление системы и обеспечивает переход от логического представления к реализации проекта в форме программного кода. Стереотипы компонентов такие: база данных DB; модуль который выполняется .