4879

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

Лекция

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

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

Русский

2012-11-28

47.5 KB

40 чел.

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

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

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

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

Алгоритм

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

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

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

В среднем

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

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

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

}


 

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

43973. Психологическое желание материнства 209 KB
  Материнство изучается в русле различных наук: истории, культурологи, медицины, физиологии, биологии поведения, социологии, психологии. Каждая наука изучает и определяет материнство, исходя из своих целей и задач. Интерес к комплексному изучению материнства появился сравнительно недавно.
43974. Проблеми функціонування промислового підприємства в умовах ринкових відносин 121.5 KB
  Собівартість продукції. Рентабельність продукції. Конкурентоспроможність продукції в ринкових умовах. В умовах ринкової економіки виживає лише той хто найбільше грамотно визначить вимоги ринку і організує виробництво продукції яка користується попитом і забезпечить високий рівень заробітної плати працівників підприємства.
43975. Зелена музика твоїх думок 30.51 MB
  Приступаючи до вибору моєї дипломної роботи я думала над тим яку роль будуть відігравати мої вироби в інтер’єрі, як вони будуть використовуватись. Мені захотілось, щоб ці керамічні твори мали як декоративне так і утилітарне призначення. Тому я вирішила обрати темою своєї дипломної роботи декоративні кашпо на тему: «Зелена музика твоїх думок».
43976. ДРАМАТУРГІЯ ЄВГЕНА ПЛУЖНИКА У КОНТЕКСТІ ЙОГО ДОБИ 345 KB
  У вирі такої провокативної і суперечливої дійсності з’явилися драматичні шедеври Євгена Павловича Плужника. Таємницю творчого феномену Євгена Плужника розгадувало чимало науковців. Жулинського дружини найближчого друга Євгена Плужника Григорія Косинки Т.
43977. Телекомунікації. Методичні вказівки 286 KB
  Дипломна робота на здобуття ступеня бакалавра по напряму 6.0924 «Телекомунікації» ставить за мету систематизацію, закріплення і розширення отриманих в процесі навчання теоретичних і практичних знань, а також оцінку підготовленості студентів до самостійної і ефективної роботи в умовах науково-технічного прогресу, економічного і культурного розвитку суспільства.
43978. Способи обробки субпродуктів. Особливості зберігання продуктів 1.35 MB
  Загальна характеристика субпродуктів 3. Способи обробки субпродуктів 5. Удосконалено технологічні процеси приготування напівфабрикатів з субпродуктів у процесі правильної технології їх виробництва первинної і теплової обробки відповідних субпродуктів. Розробляються і використовуються нові електрофізичні біотехнічні і ферментативні методи обробки субпродуктів.
43979. ОДЕРЖАННЯ ГАЛОГЕНІЗОТІОЦІАНАТІВ ТА ДОСЛІДЖЕННЯ ЇХ ВЗАЄМОДІЇ З ГІДРОКСИБЕНЗАЛЬДЕГІДАМИ 2.41 MB
  Дотримання правил техніки безпеки є обов’язковим для кожного працівника під час роботи в хімічній лабораторії. Більш досвідчені працівники мають створювати такі умови праці в лабораторії при яких було б неможливе недбале ставлення до вимог техніки безпеки. До роботи в хімічній лабораторії допускаються особи які пройшли медичне обстеження та інструктаж з техніки безпеки.
43980. Исследование вопросов оформления и учета операций в иностранной валюте банками Республики Беларусь и разработка путей их развития 403 KB
  Понятие и сущность операций в иностранной валюте. Внебиржевой порядок Основные направления развития операций в иностранной валюте в Республике Беларусь. Целью работы является исследование вопросов оформления и учета операций в иностранной валюте банками Республики Беларусь и разработка путей их развития. Исходя из поставленной цели предметом работы является порядок оформления и учета операций в иностранной валюте банками Республики Беларусь.
43981. Правила складання і оформлення актів 240.5 KB
  Сукупність взаємоповязаних документів, які застосовуються у певній сфері діяльності, становить систему документації. Нині діють уніфіковані системи. Однією з найпоширеніших є організаційно - розпорядча документація (ОРД), використовувана в оформленні управлінських рішень.