27.Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів.

Алгоритми сортування

Детальніше: Алгоритми сортування

• Сортування бінарним деревом

• Сортування Бого

• Сортування стандартним обміном (сортування бульбашкою): для кожної пари індексів, поміняти місцями невпорядковані елементи

• Сортування комірками

• Сортування змішуванням Cocktail sort

• Сортування гребінцем Comb sort (модифікація сортування бульбашкою)

• Сортування підрахунком

• Сортування гнома Gnome sort

• Flashsort

• Сортування купою: занести список у купу, видаляти найбільший елемент купи та записувати його у кінець списку

• Сортування вставкою: з'ясувати місце, на яке слід поставити поточний елемент, та вставити його туди

• Сортування вставкою з проміжками en:Library sort

• Сортування злиттям: відсортувати першу та другу половину списку окремо, а потім об'єднати їх в один список

• Pancake sorting

• Цифрове сортування Pigeonhole sort

• Швидке сортування: розділити список на дві частини, так, щоб всі елементи першої частини не перевищували елементи з іншої, відсортувати обидві частини

• Сортування за розрядами: сортування рядків літера за літерою

• Сортування вибором: обрати найменший елемент із решти списку, та перенести його в кінець відсортованої частини

• Сортування Шелла: спроба покращити сортування вставкою

• Пірамідальне сортування Smoothsort

• Топологічне сортування Topological sorting

Алгоритми пошуку

Детальніше: Алгоритми пошуку

• Лінійний пошук (Linear search): шукає елемент у не відсортованому списку

• Алгоритм вибору (Selection algorithm): знаходить k-ий найбільший елемент

• Двійковий пошук (Binary search algorithm): шукає елемен у впорядкованому списку

• Бінарне дерево пошуку (Binary search tree): використовує бінарне дерево для збереження елементів

• Пошук в ширину (Breadth-first search): обходить граф рівень за рівнем

• Пошук в глибину (Depth-first search): обходить граф гілка за гілкою

• Пошук в глибину з ітеративним заглибленням (Iterative deepening depth-first search): обходить граф гілка за гілкою щоразу збільшуючи глибину обходу

• Пошук за першим кращим збігом (Best-first search): обходить граф в порядку важливості елементів, використовуєтсья черга з пріоритетами

• Алгоритм пошуку A* (A-star search algorithm): окремий випадок пошуку за найкращим шляхом, що використовує евристику для покращення швидкодії

• Алгоритм пошуку SMA* (en:Simplified Memory-Bounded A-star search algorithm) : модифікація алгоритму А* з обмеженим використанням пам'яті

• Алгоритм пошуку D* (en:D*): вдосконалений варіант А*, враховує нову інформацію про середовище

• Пошук за критерієм вартості (Uniform-cost search): алгоритм пошуку на деревах, що знаходить найдешевший шлях

• Інтерполяційний алгоритм пошуку (Interpolation search): подібний до алгоритму двійкового пошуку

• Хеш-таблиця (Hash table): шукає елемент у невпорядкованій множині за час O(1)

циклов

Оптимизация циклов

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

Организация циклов

Цикл можно организовать при помощи условного оператора и оператора GOTO. Для этого, например, в процедуре можно объявить целочисленную переменную, которая будет служить счетчиком. Перед входом в группу операторов, подлежащих многократному выполнению (такая группа операторов называется телом цикла), счетчику присваивается значение 0. Затем следуют операторы тела цикла, среди которых необходимо обязательно разместить оператор, увеличивающий значение счетчика на 1. Завершает всю конструкцию условный оператор, в котором проверяется значение счетчика. Если оно еще не превышает заранее заданного предельного значения, то при помощи оператора GOTO осуществляется переход к первому оператору тела цикла. Операторы тела цикла выполнятся еще раз, и так будет продолжаться до тех пор, пока значение счетчика не превысит заданный предел.