Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика, программирование->Лабораторная работа
Регістр – це спеціальний запам’ятовуючий пристрій, який складається з лінійки тригерів і може запам’ятовувати декілька біт інформації одночасно. Більш...полностью>>
Информатика, программирование->Лабораторная работа
00 7.00 .00 A =A1- *A A = 0 13 1 A1=3*A1- *A3 A1 = 0 13 5 >>Anew=[A1;A ;A3] Anew = 0 13 5 0 13 1 3 7 %%4 Сгенерировать массив B размером 3 ´ 3 co случ...полностью>>
Информатика, программирование->Контрольная работа
Пусть числовые данные начинаются со второй строки. Тогда для подсчета стоимости первого товара нужно ввести в ячейку С2 формулу =А2*В2. После нажатия ...полностью>>
Информатика, программирование->Реферат
Представьте себе, что вам необходимо заполнить колонку на рабочем листе разными данными, которые зависят от значений другой колонки. Например, вы хоти...полностью>>

Главная > Лекция >Информатика, программирование

Сохрани ссылку в одной из сетей:

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

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

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

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

  • зависимость от структуры исходных данных, например, поведение алгоритма для частично упорядоченных последовательностей, требование каких-либо особенностей входной последовательности и т.д.

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

  • простота реализации, зачастую определяет выбор алгоритма в условиях ограниченного времени на разработку, отладку и тестирование алгоритма.

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

Алгоритм

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

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

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

В среднем

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

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

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

#include

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

}


Загрузить файл

Похожие страницы:

  1. Алгоритмы сортировки (2)

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

    Курсовая работа >> Информатика
    ... эффективности алгоритмов сортировки "на месте" является число необходимых сравнений в ходе сортировки и число необходимых пересылок элементов. Эффективные алгоритмы сортировки ...
  3. Быстрые алгоритмы сортировки и поиска

    Лекция >> Информатика, программирование
    ... сравнение. Тогда общее количество перестановок, осуществляемых алгоритмом, не превосходит C(n) и, следовательно, эффективные алгоритмы сортировки ... должны иметь сложность O(n log2 n) как по сравнениям, так и ...
  4. Алгоритмы сортировки (3)

    Курсовая работа >> Информатика
    ... , который достаточно мал по сравнению с сортируемым списком. Эффективность алгоритма падает всякий раз, когда ...
  5. Разработка и анализ алгоритма сортировки посредством выбора на основе разработки шаблона функции C++

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

Хочу больше похожих работ...

Generated in 0.0010530948638916