4879

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

Лекция

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

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

Русский

2012-11-28

47.5 KB

41 чел.

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

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

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

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

Алгоритм

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

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

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

В среднем

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

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

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

}


 

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

7228. Выбор и расчет рациональных способов восстановления деталей на примере толкателя клапанов тракторного двигателя 370.5 KB
  Выбор и расчет рациональных способов восстановления деталей на примере толкателя клапанов тракторного двигателя Задание Необходимо выбрать оптимальный способ восстановления детали с подробным описанием операций, расчетом времени и себестоимости...
7229. Инвестиционный проект модернизации ОАО Рыбинские моторы 209 KB
  Инвестиционный проект модернизации ОАО Рыбинские моторы В данном курсовом проекте все три фазы рассмотрены в первой части. Во второй части проекта произведен расчет наиболее выгодного источника получения денежных средств для осуществления данного пр...
7230. Разработка проекта рациональной организации поточной линии на производстве 169.62 KB
  Введение. Задачей любого предприятия является повышение качества производимой продукции или услуги при минимальных затратах на производство, поэтому тема Организация поточного производства очень актуальна, в ней я рассматриваю вопросы оптимального...
7231. Конструкция и материал оптических волокон 453 KB
  Конструкция и материал оптических волокон. Оптические волокна можно разделить на следующие типы: кварцевые, кварц-полимерные и полимерные. Кварцевые оптические волокна изготавливаются из высокочистого кварцевого стекла (сердечник и светоотражающая о...
7232. Расчет напряжений в молитных и бандажированных штампах 443 KB
  Теория обработки металлов давлением Расчет напряжений в молитных и бандажированных штампах. Исходные данные: Диаметр поковки: 115 мм Высота поковки: 90 мм Марка стали поковки: Сталь 50 Истинный предел текучести: МПа Размеры монолитного штампа....
7233. Организация работы участка по ремонту топливной аппаратуры на АТП в г. Ростове на Дону 298 KB
  Введение Перевозки автомобильным транспортом предполагают использование подвижного состава (автомобилей и автопоездов), находящегося в исправном техническом состоянии. Исправное техническое состояние означает полное соответствие подвижного состава н...
7234. Статистические оценки параметров распределения. Точечные и интервальные оценки параметров распределения 56 KB
  Статистические оценки параметров распределения Пусть требуется изучить количественный признак некоторой совокупности. Построив вариационный ряд и изобразив его графически, можно получить первоначальное представление о виде распределения....
7235. Статистическая проверка статистических гипотез 68 KB
  Лекция 3. Статистическая проверка статистических гипотез. Часто необходимо знать закон распределения генеральной совокупности. Если закон распределения неизвестен, но имеются основания предположить, что он имеет определенный вид, то выдвигают гипоте...
7236. Элементы теории корреляции 57 KB
  Лекция 4. Элементы теории корреляции. Во многих задачах требуется установить и оценить зависимость изучаемой случайной величины Y от случайной величины X. Статистической называют зависимость, при которой изменение одной из величин влечет изменение р...