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

}


 

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

7681. Матеріально-технічне забезпечення виробництва 19.41 KB
  Матеріально-технічне забезпечення виробництва МТЗ - це вид комерційної діяльності щодо забезпечення матеріально-технічними ресурсами процесу виробництва, здійснюваної, як правило, до початку виробництва. Основна мета МТЗ - доведення матері...
7682. Нормування праці 19.21 KB
  Нормування праці Нормування праці - це від діяльності з управління підприємством, пов’язаний з визначенням необхідних затрат праці та її результатів, контролем за мірою праці. Мета нормування праці в ринкових умовах полягає в тому, щоб на ...
7683. Призначення та класифікація нормативів праці 61.25 KB
  Призначення та класифікація нормативів праці. Під час нормування праці важливим завданням є забезпечення більш-менш рівної інтенсивності праці на різних за змістом та складністю роботах. Це досягається використанням єдиної методологічної (зага...
7684. Компенсаторно-приспособительные процессы 50 KB
  Компенсаторно-приспособительные процессы Определение. Приспособление (адаптация) - это процессы, с помощью которых организм реагирует на изменения условий жизни. Компенсация - это вид приспособления (адаптации) для восстановления нар...
7685. Опухоли системы крови (гемобластозы) 53.5 KB
  Опухоли системы крови (гемобластозы) Гемобластозы - опухолевые процессы кроветворной ткани. Разделяют две группы гемобластозов: лейкозы (лейкемия) - системные опухолевые заболевания кроветворной ткани. лимфомы - регионарны...
7686. Онкология. Теоретические особенности 49 KB
  Онкология Опухоль (tumor, neoplasma, blastoma) - патологический процесс, характеризующийся бесконтрольным размножением и ростом клеток, что связано с изменениями в генетическом аппарате клеток. Свойства опухоли: автономный рост опухоли...
7687. Эпителиальные органоспецифические опухоли 41 KB
  Эпителиальные органоспецифические опухоли Определение. Органоспецифические опухоли - это большая группа доброкачественных и злокачественных опухолей, которые развиваются только в определенном органе или происходят из клеток определенного органа...
7688. Мезенхимальные опухоли 49 KB
  Мезенхимальные опухоли Мезенхимальные опухоли происходят из тканей мезенхимального происхождения. Это группа включает опухоли из фиброзной, жировой, мышечной, синовиальной, мезотелиальной, костной, хрящевой тканей, а также опухоли сосудов (кро...
7689. Раки важнейших локализаций 91 KB
  Раки важнейших локализаций Актуальность темы Ежегодно число новых случаев выявления рака во всех странах мира составляет около 6 млн. человек. Уровни заболеваемости и смертности от злокачественных опухолей в разных странах и даже регионах этих стран...