4879

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

Лекция

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

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

Русский

2012-11-28

47.5 KB

42 чел.

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

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

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

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

Алгоритм

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

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

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

В среднем

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

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

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

}


 

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

68567. Конкурс професійної майстерності «Щасливий разом з дітьми» 62.5 KB
  Мета: сприяти формуванню професійної майстерності учителів школи, показати розвиток їх професійних здібностей; розвивати потребу в самовдосконаленні, саморозвитку; сприяти піднесенню їхнього авторитету. Обладнання: виставка творчих доробок учителів, що атестуються; портфоліо, плакат із висловом...
68570. ДІЄВІ ФОРМИ МЕТОДИЧНОЇ РОБОТИ З ПЕДАГОГАМИ ЗАГАЛЬНООСВІТНЬОГО НАВЧАЛЬНОГО ЗАКЛАДУ 53 KB
  Методична робота є однією з найважливіших ланок у діяльності закладу освіти оскільки забезпечує постійне навчання педагогів підвищення їх фахової майстерності знайомить із інноваційними процесами в освіті та залучає до активної творчої педагогічної діяльності
68571. Нетрадиційні форми проведення педагогічних рад. Педагогічна вітальня 60.5 KB
  Що ж таке педагогічна вітальня? Це форма методичної роботи, до якої залучаються не тільки вчителі, а й батьки, учні, представники органів місцевого самоврядування та громадських організацій. Виходячи із назви даної форми роботи «вітальня», можна зазначити, що на заходах такого типу повинні...
68572. Система научно-методической работы учебного учреждения как основа построения и реализации индивидуальной траектории профессионального развития педагога 75 KB
  Система научно-методической работы учебного учреждения как основа построения и реализации индивидуальной траектории профессионального развития педагога На современном этапе организации учебно-воспитательного процесса самым важным есть личность педагога его развитие его профессионализм.
68573. Розвиток творчого потенціалу педагога в системі науково-методичної роботи школи 83 KB
  У статті розглянуто проблему формування творчого потенціалу педагога у системі науковометодичної роботи школи. У цьому зв’язку виникає проблема вивчення розвитку і використання творчого потенціалу особистості актуалізується необхідність побудови та реалізації освітнього процесу що створює...
68574. Роль контролю, оцінювання та стимулювання навчальної діяльності у підвищенні її результативності та розвитку творчої активності учнів 217 KB
  Мета: на основі узагальнення досвіду, вивчення психолого-педагогічної літератури виявити основні причини неуспішності школярів та способи вирішення даної проблеми; з’ясувати, як впливають умови уроку на створення комфортних умов для самореалізації та самовдосконалення особистості учня й забезпечення...
68575. Найбільш типові помилки у роботі вчителів та шляхи їх подолання 536.5 KB
  Недосконалість сформованої етичної компетентності фахівця призводить до того що майбутній учитель не може правильно обрати тактику своєї поведінки. Учитель дуже тихо говорить окремі слова вимовляє нечітко учням важко стежити за ходом розповіді. Готуючись до уроку кілька разів запишіть пояснення...