4879

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

Лекция

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

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

Русский

2012-11-28

47.5 KB

38 чел.

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

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

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

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

Алгоритм

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

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

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

В среднем

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

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

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

}


 

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

35631. Творческий проект «Наряд спящей красавицы» 422.94 KB
  Последовательность изготовления ночной сорочки. Конструкция сорочки должна соответствовать выбранной модели. Ситец сатин Лён Хлопок Шёлк Ткань для ночной сорочки Мы с мамой купили ткань под название ситец Б. Раскрой ночной сорочки.
35632. Радиальный центробежный вентилятор. Творческий проект 366.86 KB
  Опыт работы показывает значительное повышение интереса учащихся к предмету если учитель привлекает на уроках при изучении различных тем наглядные пособия. Если использовать в технологическом образовании наглядные пособия которые 1 – отвечают основным характеристикам предъявляемым к таким пособиям; 2 – имеют свою сущность применения; 3 – имеют свою технологию изготовления; 4 – и для которых разработана методика применения то изучаемый материал будет усваиваться учащимися на более высоком уровне.Задачи: 1 изучить основные характеристики...
35636. Вышивка крестом. Творческий проект 64.52 KB
  Ведь если бы я умела вышивать то я смогла бы дарить красивые вышивки своим друзьям и близким. Такой рисунок вышивки как раз мне по душе. Виды швов отличаются разнообразием: для глухой вышивки по целой ткани характерны крест гладь набор роспись тамбур и др.; для строчной вышивки по ткани с предварительно вырезанными или выдернутыми на отдельных её участках нитями – мерёжка перевить настил гипюр и др.
35637. Творческий проект «Движение» 45.77 KB
  Получение базовых навыков в методике создания проектовбОсновные задачи проекта:1. Механизм и методы реализации АРеализуемый проект будет работать по следующим принципам: Использование нестандартных способов работыпроведение тематических вечеров собраний и прочего Проведение бесед тренингов дебатов для рационального использования гражданских инициатив Метод деления группы на структурные подразделения под названиямиаЕдинство для учащихся 911 кл. Методы творческой стимуляции группы: Мозговой штурм Корзина идей Метод...
35638. ФРУКТОША (Дерево из бисера.) Творческий проект 896.38 KB
  Фруктовое дерево потому что изделия из бисера во все века притягивали к себе восхищенные взоры. Чтобы изготавливать изделия из бисера не требуется специальная подготовка а достаточно лишь фантазии.Немного из истории бисера С доисторических времен и до наших дней бусины вырезанные из камня или из костей и зубов животных вызывали огромный интерес.