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

}


 

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

45481. Аспекты информатизации образования 43 KB
  Компьютерные программы и обучающие системы представляющие собой: компьютерные учебники предназначенные для формирования новых знаний и навыков; диагностические или тестовые системы предназначенные для диагностирования оценивания и проверки знаний способностей и умений; тренажеры и имитационные программы представляющие тот или иной аспект реальности отражающие его основные структурные и функциональные характеристики и предназначенные для формирования практических навыков; лабораторные комплексы в основе которых...
45482. ИТ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ 132 KB
  Наиболее полно возможности САПРпродукта на уровне универсального графического пакета можно проследить на примере utoCD 2000 новой версии самого популярного в России чертежного пакета.; наличие средств моделирования позволяющих редактировать твердотельные объекты на уровне ребер и граней; возможность обращения к свойствам объектов; возможность выбора группировки и фильтрации объектов по типам и свойствам; наличие технологии создания и редактирования блоков; возможность вставки в чертеж гиперссылок; включение...
45484. ФОРМИРОВАНИЕ МОДЕЛИ ПРЕДМЕТНОЙ ОБЛАСТИ 4.08 MB
  Таким образом для современного состояния информационных технологий необходим переход от информационного описания предметной области к представлению на уровне данных осуществляемый на основе декомпозиции абстракции агрегирования. При анализе предметной области принято выделять три этапа: анализ требований и информационных потребностей; определение информационных объектов и связей между ними; конструирование концептуальной модели предметной области. Этап анализа требований и информационных потребностей включает следующие задачи:...
45485. Объектно-ориентированная технология проектирования ИС 52 KB
  В основу объектноориентированной технологии проектирования ИС положены разработка анализ и спецификация концептуальной объектноориентированной модели предметной области. Концептуальная объектноориентированная модель предметной области является основой проекта и реализации системы и обеспечивает: необходимый уровень формализации описания проектных решений; высокий уровень абстрагирования типизации и параметризации проектных решений; компактность описания; удобство сопровождения готовой системы. Отличительными...
45486. ОЦЕНКА КАЧЕСТВА ИНФОРМАЦИОННЫХ СИСТЕМ 75 KB
  В настоящее время наибольшее распространение получила иерархическая модель взаимосвязи компонент качества ИС. В начале определяются характеристики качества в числе которых. Каждому показателю качества ставится в соотвествие группа критериев.
45487. ПРОГРАММНЫЕ СРЕДСТВА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 76.5 KB
  Базовые программные средства относятся к инструментальной страте информационных технологий и включают в себя: операционные системы ОС; языки программирования; программные среды; системы управления базами данных СУБД. Большинство алгоритмических языков программирования Си Паскаль созданы на рубеже 60х и 70х годов за исключением Jv. За прошедший период времени периодически появлялись новые языки программирования однако на практике они не получили широкого и продолжительного распространения. Другим направлением в эволюции...
45488. ТЕХНИЧЕСКИЕ СРЕДСТВА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 75.5 KB
  Для преодоления ограничений организации памяти были предложены ассоциативные запоминающие устройства. Вторая характеристика определяется скоростью доступа устройства чтения к информации на компактдиске скорость чтения особенно важна при воспроизведении аудио и видеоинформации. Что означает название восьмискоростной CDROM Это и есть характеристика быстродействия устройства чтения.
45489. МЕТОДИЧЕСКИЕ СРЕДСТВА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 47.5 KB
  Многообразные стандарты и подобные им методические материалы упорядочим по следующим признакам: 1. По утверждающему органу: официальные международные стандарты; официальные национальные стандарты; национальные ведомственные стандарты; стандарты международных комитетов и объединений; стандарты фирмразработчиков; стандарты дефакто. По предметной области стандартизации: функциональные стандарты стандарты на языки программирования интерфейсы протоколы кодирование шифрование стандарты на фазы...