4879

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

Лекция

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

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

Русский

2012-11-28

47.5 KB

39 чел.

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

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

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

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

Алгоритм

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

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

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

В среднем

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

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

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

}


 

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

26884. Морфофункциональная характеристика черепно-мозговых нервов 4.77 KB
  морфофункциональная характеристика черепномозговых нервов Каждый отдел головного мозга человека исторически связан с конкретными дистантными анализаторами хеморецепторами фоторецепторами тактильными или слуховыми системами анализа внешней и внутренней среды организма. Как правило рецепторы расположены на некотором расстоянии от мозга и соединены с ним посредством нервов. Черепные нервы устаревшее название черепномозговые нервы двенадцать пар нервов выходящих из мозгового вещества в основании мозга и иннервирующих структуры...
26885. V-я и VI 1-я пары черепно-мозговых нервов. Общая характеристика, ветвление 2.98 KB
  Двенадцать пар черепномозговых нервов принято делить на 3 чувствительных I пара обонятельный U пара зрительный и VIII пара преддверноулитковый 5 двигательных III пара глазодвигательный IV пара блоковый VI пара отводящий XI пара добавочный и XII пара подъязычный и 4 смешанных V пара тройничный VII пара лицевой IX пара языкоглоточный и X пара блуждающий; в состав последних входят чувствительные двигательные и вегетативные волокна. 5 пара тройничный нервn.
26886. Общие закономерности строения вегетативной нервной системы 2.13 KB
  В симпатической нервной системе преганглионарные нейроны находятся в промежуточном боковом роге спинного мозга от верхнегрудного до среднепоясничного отдела Т1ТЗ. Преганглионарные парасимпатические нейроны залегают в стволе мозга и крестцовом отделе спинного мозга. Постганглионарные нейроны находятся в вертебральных и превертебральных ганглиях в симпатической системе а в парасимпатической они расположены в непосредственной близости от стенки органа который они иннервируют.
26887. Симпатическая часть вегетативной нервной системы. Солнечное сплетение 4.18 KB
  Симпатическая нервная система делится на центральную расположенную в спинном мозге и периферическую включающую многочисленные соединённые друг с другом нервные ветви и узлы. По своему ходу симпатические волокна отделяются от двигательных соматических и далее в виде белых соединительных ветвей вступают в узлы пограничного симпатического ствола. В состав солнечного сплетения входят правый и левый чревные узлы непарный верхний брыжеечный узел большой и малый внутренностные нервы и многие другие которые отходят от узлов в разные стороны...
26888. Парасимпатическая часть вегетативной нервной системы 4.21 KB
  Преганглионарные волокна отходят от центров в составе черепномозговых или спинномозговых нервов. От центров расположенных в среднем мозге преганглионарные волокна доходят до ресничного узла а от него идут постганглионарные волокна к глазу где разветвляются в сфинкторе зрачка и ресничной мышце.Слезоотделительныйпреганглиолярные волокна доходят до клинонёбного ганглия постганглиолярные волокна достигают слёзных желёз желёз неба и носовой полости; 2.Краниальныйоральный слюноотделительный – преганглиолярные волокна доходят до...
26889. Блуждающий нерв 4.81 KB
  Направляясь латерально и вниз он покидает череп через переднюю часть яремного отверстия вместе с языкоглоточным и добавочным нервами располагаясь между ними. В области яремного отверстия блуждающий нерв утолщается за счёт верхнего узла лат. ganglion superius а немного ниже через 1015 см имеется ещё один узел несколько больших размеров лат. Спускаясь ниже блуждающий нерв в области шеи ложится на переднюю заднюю поверхность внутренней яремной вены лат.
26891. Защитные и вспомогательные образования глаза 1.53 KB
  Защитные и вспомогательные образования глаза К защитным и вспомогательным приспособлениям глаза относятся орбита глазной жир мышцы глаза веки ресницы конъюнктива слезный аппарат. Орбита является костным остовом глаза и защищает глазное яблоко от механических воздействий. Из коньюнктивального мешка слеза оттекает по носослезному каналу который начинается от слезного мешка во внутреннем углу глаза а заканчивается отверстием на слизистой оболочке носовой полости у входа.
26892. Оболочки и светопреломляющие среды глазного яблока 3.11 KB
  Наружная оболочка глазного яблока соединительнотканного происхождения и делится на две части склеру и роговицу. Склераsclera или белочная оболочка толстая прочная непрозрачная расположена в заднем отделе глазного яблока. Средняя сосудистая оболочка в которой в большом количестве разветвляются сосуды также делится на заднюю собственно сосудистуюchorioidea и переднюю части. В собственной сосудистой оболочке находится отражательная оболочкаtapetum.