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

}


 

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

58452. Їжа. Food. Dishes 51.5 KB
  This is a picture of our New Years party. This is my family: My Mum, Dad, my little sister Ann and our dog. Mum is watching TV/eating the cake. Dad is watching TV/sleeping. Ann is singing/dancing. She looks happy!
58453. Застосування загального правила додавання двоцифрових чисел до обчислень виду 54 + 30, 54 + 3 47 KB
  Мета. Формувати вміння застосовувати загальне правило додавання двоцифрових чисел до окремих випадків, коли в одному із компонентів цих дій відсутні десятки або одиниці; закріплювати вміння розвязувати задачі.
58454. Вторая война Рима с Карфагеном (218-201 гг. до н.э.) 57 KB
  Это выдающийся карфагенский полководец Ганнибал. С детских лет Ганнибал готовился к войне с римлянами. Ганнибал произнес вслед за ним: Клянусь что я никогда не буду другом римлян и сделаю им столько зла сколько смогу Ганнибал до самой смерти остался верен этой клятве. Ганнибал был образованным человеком.
58457. Общая характеристика продукции 122.5 KB
  Общая характеристика продукции Результат труда чаще выступает в материальной форме в виде продукции. Изготавливаемая на предприятии продукция на разных стадиях технологического процесса находится в виде незавершенного производства полуфабриката или готового изделия продукции. Незавершенное производство это продукция не получившая законченного вида в пределах производства а также продукция не проверенная ОТК и не сданная на склад готовой продукции. Планирование и учет изготовлений продукции осуществляется в натуральных...
58458. РАДІОПРИЙМАЛЬНИЙ ПРИСТРІЙ РАДІОЛОКАЦІЙНИХ СИГНАЛІВ З РОЗРАХУНКОМ ПІДСИЛЮВАЧА ВИСОКОЇ ЧАСТОТИ 104.5 KB
  о складу системи входять джерело радіовипромінювання, лінія передачі та радіоприймальний пристрій. Джерело радіовипромінювання може удавати з себе або радіопередавальний пристрій або пасивний відбива
58459. Электроустановки с изолированными и глухозаземленными нейтралями 174 KB
  Вид связи нейтралей машин и трансформаторов с землей в значительной степени определяет уровень изоляции электроустановок и выбор коммутационной аппаратуры значения перенапряжений и способы их ограничения токи при однофазных замыканиях на землю условия работы релейной защиты и безопасности...
58460. Организация и порядок проведения капитальных ремонтов 41.5 KB
  Планово-предупредительный ремонт представляет собой комплекс работ, направленных на поддержание и восстановление работоспособности оборудования путем обслуживания, ремонта и замены изношенных деталей и узлов с тем, чтобы в дальнейшем обеспечить его надежную и экономичную работу.