Алгоритмы сортировки и поиска Выполнил Блинов В.А.

Библиотека STL Адаптеры Функциональные объекты

Алгоритмы STL STL - алгоритмы представляют набор готовых функций, которые могут быть применены к STL коллекциям и могут быть подразделены на три основных группы Поиска Математические Сортировки Работы С последовательностями

Функции для сортировки членов коллекции Sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search, lower_bound, upper_bound, equal_range, merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference, make_heap, push_heap, pop_heap, sort_heap, min, max, min_element, max_element, lexographical_compare, next_permutation, prev_permutation

Классификация алгоритмов в зависимости от ассимтотической сложности О(1) – постоянные (проверка числа на четность или нечетность); О(n) – линейные (find, search и др); О(logn)– логарифмические(Двоичная сортировка) О(nlogn)-квазилинейные(сортировка Шелла, Быстрая сортировка) O(n 2 )-квадратичные О(2 n )-экспоненциальные

Время выполнения алгоритмов Сложность алгоритмаn=10n=10 3 N=10 6 Logn0.2сек0.6сек1.2сек n0.6сек1час16.6час n2n2 6сек16.6час1902года 2n2n 1час лет лет

Важность использования быстрых алгоритмов С увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершается за приемлемое время. Таким образом, увеличивается среднее значение величины, и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем больше относительный проигрыш при использовании плохого алгоритма!

Критерии оценки алгоримов Время основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение это O(n log n) и плохое поведение это O(n²). Идеальное поведение для упорядочения O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем; Память ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

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

Линейный поиск Даный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева нарпаво, т.е. от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым. двоичного поиска

Линейный поиск Если отрезок имеет длину N, то найти решение с точностью до ε можно за время. Т.о. асимптотическая сложность алгоритма - O(n). В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.

Линейный поиск Линейный поиск может быть реализован с помощью STL функции FIND Пример: list L; L.push_back(3); L.push_back(1); L.push_back(7); list ::iterator result = find(L.begin(), L.end(), 7); assert(result == L.end() || *result == 7);

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

Двоичный поиск Двоичный поиск числа 9 в отсортированном массиве 1 2 3

Двоичный поиск С++ Реализация двоичного поиска с помощью STL функции BINARY_SEARCH int main() { int A[] = { 1, 2, 3, 3, 3, 5, 8 }; const int N = sizeof(A) / sizeof(int); for (int i = 1; i

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

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

Сортировка выбором template void selection_sort(vector & v) { for (int i = 0; i < v.size() - 1; i++) { int best = i; for (int j = i + 1; j < v.size(); j++) { if (v[j] < v[best]) { best = j; if (best != i) { T temp = v[i]; v[i] = v[best]; v[best] = temp;

Быстрая сортировка Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов. Метод основан на подходе "разделяй-и- властвуй".

Быстрая сортировка Общая схема : из массива выбирается некоторый опорный элемент a[i], запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо, теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого, для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру. В конце получится полностью отсортированная последовательность.

Быстрая сортировка Рассмотрим работу процедуру разделения для массива a[0]...a[6] и опорного элемента p = a[3].

Быстрая сортировка SORT Быстрая сортировка с помощью STL функции SORT int A[ ] = {1, 4, 2, 8, 5, 7}; const int N = sizeof(A) / sizeof(int); const int N = sizeof(A) / sizeof(int); sort(A, A + N); sort(A, A + N); copy(A, A + N, ostream_iterator (cout, " ")); copy(A, A + N, ostream_iterator (cout, " ")); // The output is " ". // The output is " ".

Сортировка Шелла Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.

Сортировка Шелла Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]),..., (a[7], a[15]). 2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]),..., (a[3], a[7], a[11], a[15]).

Сортирока Шелла 3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]). 4. В конце сортируем вставками все 16 элементов.

.