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

}


 

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

82172. Изучение особенностей института наследования в Российском гражданском праве 1.29 MB
  Актуальность исследования. Институт наследования возник несколько тысячелетий назад с появлением частной собственности. Упоминание о наследовании можно найти в самых первых письменных источниках: глиняных табличках Шумера, египетских папирусах и др.
82173. Разграничение доведение до самоубийства от других смежных преступлений 161.76 KB
  Социальная обусловленность уголовной ответственности за доведение до самоубийства. История ответственности за доведение до самоубийства в российском уголовном законодательстве. Для более подробного изучения вопроса об ответственности за доведение до самоубийства необходимо обратиться к истории...
82174. Розробка ІС «Рецепты для домохозяек» 247 KB
  Основне завдання інформаційної системи управління полягає у підпорядкуванні всіх внутрішніх процесів головним цілям організації. Для цього необхідно скоординувати процеси, пов’язані з діяльністю організації таким чином, щоб вони максимально забезпечували виконання поставлених задач в єдиному інформаційному полі.
82175. ПРОЕКТИРОВАНИЕ ВНУТРИЦЕХОВОГО ЭЛЕКТРОСНАБЖЕНИЯ 369.4 KB
  Выбор способа прокладки линий осветительной сети цеха В производственных участках групповые и распределительные линии прокладываются открыто по строительным конструкциям. Во вспомогательных помещениях осветительные линии прокладываются скрыто в трубах под слоем штукатурки и гофрированной пластмассовой...
82176. Проектирование и расчет параметров сетей передачи данных 10.04 MB
  Сегодня вычислительные сети продолжают развиваться, причем достаточно быстро. Разрыв между локальными и глобальными сетями постоянно сокращается во многом из-за появления высокоскоростных территориальных каналов связи, не уступающих по качеству кабельным системам локальных сетей.
82177. Физические процессы на поверхности твердых тел при лазерном воздействии 1.11 MB
  Создание лазеров совершило революцию в науке и технике. Но наиболее массовой областью использования лазерной техники является в настоящее время лазерная обработка материалов в основе которой лежит в большинстве случаев тепловое воздействие лазерного излучения.
82179. Выявление основных принципов управления в автомобилестроительных организациях 835 KB
  В процессе работы над курсовым проектом мы поставили перед собой следующие задачи: на примерах самых успешных компаний в области автомобиле строения рассмотреть модели организационных структур, позволивших этим компаниям добиться поразительных результатов и стать лидерами в этой отрасли...
82180. Анализ фондоотдачи (на примере ООО «Савой») 960.5 KB
  Данная тема курсовой работы актуальна, так как интенсивность и эффективность использования основных средств как скрытый резерв предприятия определяет доходность капитала и финансовое состояние предприятия.