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

}


 

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

72140. Образование СССР. Советские республики в 1921-1922 гг.: необходимость, возможности и трудности объединения. Первый Всесоюзный Съезд Советов (30 декабря 1922 г.) 32 KB
  Для начала нужно выделить предпосылки образования СССР: однотипная экономика давние хозяйственные связи разделение труда между народами; смешанное население прочные родственные связи природа советской власти дружественные отношения; однотипная власть советы; единая партия РКПб единая армия...
72141. Присоединение Прибалтики к России. Эстляндия и Лифляндия в составе России 33 KB
  Прибалтика, состоящая из Эстляндии, Курляндии и Лифляндии, была присоединена к России в ходе Северной войны (1700-1721), которую вела Россия со Швецией за выход к Балтийскому морю. В результате победы России, по Ништадтскому мирному договору 1721 г., в состав империи вошли Эстония...
72142. Административные наказания 45.5 KB
  Установлено и новое административное взыскание административное выдворение за пределы Российской Федерации иностранного гражданина или лица без гражданства. Административное выдворение за пределы Российской Федерации иностранных граждан и лиц без гражданства заключается в принудительном...
72143. Понятие и принципы гражданского процессуального права 32.5 KB
  Таким образом нормы этой отрасли права регламентируют общественные отношения возникающие в сфере гражданского судопроизводства гражданско-процессуальные отношения. Следует иметь в виду что в рамках гражданского судопроизводства обеспечивается реализация норм не только гражданского но и ряда других...
72144. Подведомственность и подсудность 22.5 KB
  Между ними дела распределяются следующим образом. К ведению общих судов относятся независимо от того из каких правоотношений возник спор все дела одной из сторон в которых выступает гражданин. Арбитражные суды рассматривают преимущественно дела связанные с разрешением хозяйственных споров...
72145. Стадии гражданского процесса 23 KB
  Стадия гражданского процесса – совокупность процессуальных действий, направленных к одной ближайшей цели: принятие заявления, подготовка дела к судебному разбирательству, судебное разбирательство и т.д.
72146. Понятие и принципы уголовно-процессуального права 36 KB
  В наибольшей степени регламентирована правовыми нормами уголовно-процессуальная деятельность. Это обусловлено, с одной стороны, тем, что из всех правонарушений именно преступления представляют наибольшую опасность для общества и особенно важно их раскрытие и наказание виновных...
72147. Стадии уголовного процесса 26.5 KB
  Процессуальные стадии это сменяющие друг друга части ступени развития юридического процесса. Так в уголовном процессе обычно выделяют следующие стадии: возбуждения уголовного дела; предварительного расследования; подготовки к судебному разбирательству; судебного разбирательства; кассационного рассмотрения...
72148. Володимир Володимирович Маяковський 79 KB
  Маяковському, щоб описати краще сучасників, необхідно було вчитися майстерності. І він вирішує покинути ряди партії, щоб знаходитися на легальному становищі. Першим ділом береться за живопис, навчається у Жуковського. Через рік починає освоювати рукоділля у Келіна.