Алгоритмы — Dart

Все алгоритмы реализованы на Dart (для обучения)

Эти реализации предназначены для учебных целей. Они могут быть менее эффективными, чем реализации в стандартной библиотеке Dart.

Список алгоритмов

Полный список всех алгоритмов можно найти в нашем каталоге. Здесь объясняются некоторые из алгоритмов (наиболее распространённые).

Алгоритмы поиска

Линейный

Из Википедии: линейный поиск или последовательный поиск — это метод нахождения целевого значения в списке. Он последовательно проверяет каждый элемент списка на соответствие целевому значению до тех пор, пока не будет найдено совпадение или пока все элементы не будут проверены. Линейный поиск выполняется за наихудшее линейное время и делает не более n сравнений, где n — длина списка.

Свойства

• Наихудшая производительность O(n)
• Лучшая производительность O(1)
• Средняя производительность O(n)
• Пространственная сложность в худшем случае O(1), итеративный

Двоичный

Из Википедии: двоичный поиск, также известный как полуинтервальный поиск или логарифмический поиск, — это алгоритм поиска позиции целевого значения внутри отсортированного массива. Он сравнивает целевое значение со средним элементом массива; если они не равны, исключается половина, в которой целевое значение не может находиться, и поиск продолжается в оставшейся половине до тех пор, пока он не будет успешным.

Свойства

• Наихудшая производительность O(log n)
• Лучшая производительность O(1)
• Средняя производительность O(log n)
• Пространственная сложность в худшем случае O(1)

Сортировочные алгоритмы

Пузырьковый

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

Свойства

• Наихудшая производительность O(n^2)
• Лучшая производительность O(n)
• Средняя производительность O(n^2)

Посмотреть алгоритм в [действии][bubble-toptal]

Вставка

Из Википедии: сортировка вставками — это простой алгоритм сортировки, который строит окончательный отсортированный массив (или список) по одному элементу за раз. Он гораздо менее эффективен для больших списков, чем более продвинутые алгоритмы, такие как быстрая сортировка, пирамидальная сортировка или сортировка слиянием.

Свойства

• Наихудшая производительность O(n^2)
• Лучшая производительность O(n)
• Средняя производительность O(n^2)

Посмотреть алгоритм в [действии][insertion-toptal]

Быстрая

Из Википедии: быстрая сортировка (иногда называемая сортировкой с разделением) — это эффективный алгоритм сортировки, служащий систематическим методом размещения элементов массива в порядке.

Свойства

• Наихудшая производительность O(n^2)
• Лучшая производительность O(n log n) или O(n) с трёхсторонним разбиением
• Средняя производительность O(n^2)

Посмотреть алгоритм в [действии][quick-toptal]

Выбора

Из [Википедии][selection-wiki]: алгоритм делит входной список на две части: подсписок уже отсортированных элементов, который строится слева направо в начале (слева) списка, и подсписок оставшихся элементов, которые нужно отсортировать и которые занимают остальную часть списка. Первоначально,

[selection-wiki]: https://ru.wikipedia.org/wiki/Пирамидальная_сортировка Отсортированный подсписок пуст, а неотсортированный подсписок представляет собой весь входной список. Алгоритм работает следующим образом: он находит наименьший (или наибольший, в зависимости от порядка сортировки) элемент в неотсортированном подсписке, меняет его местами с крайним левым элементом из неотсортированного списка (помещая его в отсортированный порядок) и сдвигает границы подсписка на один элемент вправо.

Свойства:

• худшая производительность — O(n^2);
• лучшая производительность — O(n^2);
• средняя производительность — O(n^2).

Посмотреть алгоритм в действии.

Слияние

Из Википедии: сортировка слиянием (также часто пишется как mergesort) — это алгоритм «разделяй и властвуй», который был изобретён Джоном фон Нейманом в 1945 году. Алгоритм сначала делит список на наименьшую единицу (1 элемент), затем сравнивает каждый элемент со смежным списком для сортировки и объединения двух смежных списков. Наконец, все элементы сортируются и объединяются. Это эффективный, универсальный алгоритм сортировки на основе сравнения.

Свойства:

• худшая производительность — O(n log n);
• лучшая производительность — O(n log n);
• средняя производительность — O(n log n).

Посмотреть алгоритм в действии.

Шелл

Из Википедии: Shellsort — это обобщение алгоритма сортировки вставками, которое позволяет обменивать элементы, находящиеся далеко друг от друга. Идея состоит в том, чтобы упорядочить список элементов так, чтобы, начиная с любого места, рассмотрение каждого n-го элемента давало отсортированный список. Такой список называется h-отсортированным. Эквивалентно, его можно рассматривать как h чередующихся списков, каждый из которых отсортирован по отдельности.

Свойства:

• худшая производительность — O(nlog2 2n);
• лучшая производительность — O(n log n);
• средняя производительность зависит от последовательности промежутков.

Посмотреть алгоритм в действии.

Графики временной сложности

Сравнение сложности алгоритмов сортировки (пузырьковая сортировка, сортировка вставками, сортировка выбором).

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

Вклад

Пожалуйста, ознакомьтесь с нашим CONTRIBUTING.md.

Лицензия

MIT