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

}


 

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

11741. Работа с транзакциями. Кэширование изменений при работе с транзакциями 15.39 KB
  Лабораторная работа №1415 Работа с транзакциями. Кэширование изменений при работе с транзакциями. Цель: формирование практических умений и навыков работы с операторами TransactSQL объединенных транзакцией; создания транзакций; сохранения изменений; выполнение операций
11742. Обеспечение достоверности данных и перехват исключительных ситуаций 14.27 KB
  Лабораторная работа №16 Обеспечение достоверности данных и перехват исключительных ситуаций Цель: формирование практических умений и навыков определения и назначения определенного вида блокировки при работе с транзакциями; типа объекта для осуществления синхрониз
11743. Работа с отчетами 16.13 KB
  Лабораторная работа №17 Работа с отчетами Цель: формирование практических умений и навыков построения отчетов определение и составление запросов необходимых для содержания отчета. Ход работы Задание 1: Составить 3 запроса и сделать для них отчет: В Word Со
11744. Установка привилегий доступа 15.53 KB
  Лабораторная работа №18 Установка привилегий доступа Цель: формирование практических навыков в создании пользователей полей с помощью transactSQL. Установление привилегий пользователя роли обмена и изменение привилегий указанных для пользователя. Ход работы: Зада
11745. Автоматизированное тестирование 311.5 KB
  Лабораторная работа № 7. Автоматизированное тестирование. Цель: закрепить учебные навыки по автоматизированному тестированию. Ход работы 1. procedure TForm1.Button1ClickSender: TObject; VAR a: array [1..3] of real; zssum:real; ixns1:integer; begin n:=STRTOINTedit1.Text; x:=1; z:=0; s1:=10; For i:= 1 to 3 do begin ...
11746. Использование методов защиты информации в программах 99 KB
  ЛАБОРАТОРНАЯ РАБОТА № 8. Использование методов защиты информации в программах. Цель работы: освоить на практике методы защиты информации. Ход работы 1. Написать программу которая с использованием криптосистемы RSA шифрут сообщение: Истоpия кpиптогpафии pовесница
11747. Работа в составе бригады 42 KB
  Лабораторная работа №10. Работа в составе бригады. Цель: научиться коллективно обрабатывать разрабатывать отлаживать программные продукты. Ход работы Разработать программу выполняющую вычислительные действия над комплексными числами . var Form1: TForm1; ...
11748. Научиться пользоваться системой отладки 14.07 KB
  Лабораторная работа № 7. Автоматизированное тестирование. Цель: научиться пользоваться системой отладки. Выполнил: Романов П.Н. Группа: 091ПО Преподаватель: Кашталинская И.А. Дата: 30.11.12 Ход работы: Задание № 1. Составить программу вычислени
11749. Работа с БД. Создание сложных запросов 1.04 MB
  Лабораторная работа №4 Тема: Работа с БД. Создание сложных запросов Теоретический материал Современные информационные системы основанные на концепции интеграции данных характеризуются огромными объемами хранимых данных сложной организацией необходимостью у