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

}


 

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

7404. Публічна служба в Україні:організація та функціонування 222 KB
  Публічна служба в Україні:організація та функціонування Вступ На сучасному етапі розвитку державотворення в українському суспільстві гостро постали питання стосовно того, що можна вважати публічним управлінням, чим воно відрізняється від державного ...
7405. Система органів державної влади та місцевого самоврядування в Україні 210 KB
  Система органів державної влади та місцевого самоврядування в Україні Вступ На сьогодні питання про систему органів державної влади та місцевого самоврядування, їх взаємодії є актуальним. Принцип місцевого самоврядування є однією з найважливіших озн...
7406. Державне управління. Відповіді на іспит 737 KB
  Екзаменаційні питання ДУ Управління як суспільне явище, еволюція його змісту та багатогранність. Сутність, зміст і специфіка державного управління. Державне управління як наука та навчальна дисципліна...
7407. Аналіз практичного застосування Закону України Про боротьбу з корупцією 50 KB
  Аналіз практичного застосування Закону України Про боротьбу з корупцією Корупція - це глобальна проблема, але різні країни піддаються корупції різною мірою. Рівень корумпованості країни залежить від її політичної, економічної, та соціальної сит...
7408. Стан і перспективи організаційно-правового забезпечення протидії та запобігання корупції в Україні 81.5 KB
  Стан і перспективи організаційно-правового забезпечення протидії та запобігання корупції в Україні Однією з найгостріших проблем українського суспільства за роки проведення соціально-економічних реформ у напрямі подальшої демократизації суспільного ...
7409. Чи дійсно потрібен новий закон про протидію корупції 62.5 KB
  Чи дійсно потрібен новий закон про протидію корупції? Обставина, що чинне вітчизняне антикорупційне законодавство потребує свого вдосконалення, не викликає сумніву. Хоча, зауважимо, що в системі складових ефективної протидії корупції законодавча баз...
7410. Корупція. Корупційні злочини та стан хабарництва в Україні 264.5 KB
  ПЛАН: Вступ. Розділ 1. Загальна характеристика поняття корупція. Етимологія слова корупція. Наукове розуміння поняття корупція. Нормативно-правове розуміння корупції. Розділ 2. Корупцій...
7411. Відставка державного службовця в Україні та порядок її здійснення 235 KB
  Вступ Реалізація положень Конституції України і успішне здійснення завдань держави, пов’язаних із її розвитком, соціально-економічними і ринковими перетвореннями, значною мірою залежить від професійного та сумлінного виконання державними ...