Зачем нужны алгоритмы сортировки в программировании

Что такое алгоритмы в программировании

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

Алгоритмы нужны для:

1. Получения результата более эффективным и быстрым путем
2. Уменьшения количества ошибок, которые возникают при решении задач вручную
3. Переиспользования, чтобы не «изобретать велосипед».

Алгоритмы окружают нас повсюду, в том числе и в быту:

1. Рецепт борща
2. Инструкция по сборке мебели
3. Набор действий для оплаты товаров на маркетплейсах
4. План обучения в колледже
5. Создание учетной записи.

В программировании алгоритмы используются для автоматизации процессов и упрощения решения задач, например в:

1. Сортировке и поиске данных в массивах и базах данных
2. Тестировании выпускаемого программного продукта
3. Разработке игр и приложений, чтобы определять поведение персонажей и реагировать на действия пользователя
4. Криптографии для защиты данных в системах безопасности и шифровании информации при передаче по сети
5. Системах рекомендаций для пользователей
6. Научных и медицинских исследованиях
7. Разработке искусственного интеллекта и в машинном обучении, чтобы обучать компьютеры распознавать образы и голосовые команды.

Свойства алгоритмов

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

function sumNumbers(numbers) < let sum = 0; for (let i = 0; i < numbers.length; i++) < sum += numbers[i]; >return sum; > 

Этот алгоритм принимает входной массив чисел и возвращает их сумму. Он состоит из последовательных шагов, таких как присвоение переменной sum значение равное 0, использование цикла for для прохода по элементам массива, и увеличение значения переменной sum на каждой итерации цикла.

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

2. Результативность: алгоритм всегда завершается и возвращает правильный результат.

function findMax(numbers) < let max = numbers[0]; for (let i = 1; i < numbers.length; i++) < if (numbers[i] >max) < max = numbers[i]; >> return max; > 

Алгоритм принимает входной массив чисел и возвращает максимальное число в массиве. Он начинается с инициализации переменной max первым элементом массива numbers. Затем он проходит циклом for по оставшимся элементам массива и сравнивает каждый элемент с текущим максимальным значением max. Если текущий элемент больше, то он становится новым максимальным значением.

После прохождения цикла алгоритм возвращает максимальное значение max. Таким образом, этот алгоритм всегда завершается и возвращает правильный результат, что демонстрирует его свойство результативности.

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

function isPalindrome(str) < const transitions = < 0: < '': 0, 'a': 1, 'b': 2 >, 1: < '': 3, 'a': 1, 'b': 4 >, 2: < '': 3, 'a': 4, 'b': 2 >, 3: < '': 5 >, 4: < '': 5 >, 5: <> >; let state = 0; for (let i = 0; i < str.length; i++) < const input = str[i]; if (!transitions[state][input]) < return false; >state = transitions[state][input]; > return state === 3 || state === 4; > console.log(isPalindrome('ababa')); // true console.log(isPalindrome('abab')); // false 

Код выше — реализация конечного автомата. Он проверяет, является ли заданная строка палиндромом (строка читается одинаково справа налево и слева направо).

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

4. Массовость: алгоритм должен работать для любого количества входных данных, при этом больший объем данных не будет значительно увеличивать время обработки. Например:

function sumArray(arr) < let sum = 0; for (let i = 0; i < arr.length; i++) < sum += arr[i]; >return sum; > const array1 = [1, 2, 3, 4, 5]; const array2 = Array.from(, () => Math.floor(Math.random() * 100)); console.time('sumArray1'); console.log(sumArray(array1)); console.timeEnd('sumArray1'); console.time('sumArray2'); console.log(sumArray(array2)); console.timeEnd('sumArray2'); 

Алгоритм принимает массив чисел и возвращает их сумму. Он использует цикл for, чтобы перебрать все элементы массива и добавить их к переменной sum. Функция console.time используется для измерения времени выполнения алгоритма.

Для сравнения имеются два массива: array1, который содержит всего 5 элементов, и array2, который содержит 1 миллион элементов. Однако, благодаря использованию цикла for, время выполнения алгоритма остается примерно одинаковым в обоих случаях.

5. Понятность: алгоритм должен быть понятен для исполнителя и других программистов, которые могут его использовать. Вспомним пример, который уже приводился выше:

function findMax(numbers) < let max = numbers[0]; for (let i = 1; i < numbers.length; i++) < if (numbers[i] >max) < max = numbers[i]; >> return max; > 

А теперь сравним с другим примером:

function hrleh(oooo) < let m = oooo[0]; for (let g = 1; g < oooo.length; g++) < if (oooo[g] >m) < m = oooo[g]; >> return m; > 

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

6. Конечность: алгоритм должен иметь определенное количество шагов, которые он выполняет, и в конце концов завершаться.

Приведенный выше алгоритм складывает все числа в массиве numbers. Он имеет конечное количество шагов: он просто проходит по каждому элементу массива и складывает его с общей суммой. Как только он проходит все элементы массивы, он возвращает общую сумму.

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

Виды алгоритмов

1. Линейные: действия выполняются по порядку, друг за другом. Например:

function sum(numbers) < let total = 0; for (let i = 0; i < numbers.length; i++) < total += numbers[i]; >return total; > 

Алгоритм начинается с первого элемента массива и последовательно выводит каждый элемент в консоль. Он выполняет действия по порядку без пропусков или повторений. Как только последний элемент массива будет выведен, алгоритм завершится.

2. Ветвящиеся: выполнение различных операций в зависимости от входящих условий. Например:

if (number > 0) < console.log("Число больше нуля"); >else if (number === 0) < console.log("Число равно нулю"); >else

Этот алгоритм проверяет значение переменной number и выводит различный текст в зависимости от того, какое значение имеет переменная. Если number больше нуля, то выводится сообщение «Число больше нуля». Если number равно нулю, то выводится сообщение «Число равно нулю». Если number меньше нуля, то выводится сообщение «Число меньше нуля». Это пример ветвящегося алгоритма, потому что он делает различные ветвления в зависимости от значения переменной number.

3. Циклические: повторение операций несколько раз. Изучим цикл, который повторяется, пока переменная i меньше пяти:

let i = 0; while (i

Каждый раз, когда цикл выполняется, он выводит значение переменной i на консоль и увеличивает ее на единицу. Как только переменная i достигает значения 5, цикл завершается. Это пример циклического алгоритма, потому что он выполняет повторяющиеся действия в цикле, пока не будет выполнено определенное условие.

4. Рекурсивные: вызов алгоритма из самого себя. Рассмотрим рекурсию для вычисления факториала числа n:

function factorial(n) < if (n === 1) < return 1; >else < return n * factorial(n - 1); >> console.log(factorial(5)); // 120 

Если n равно 1, то функция возвращает 1. В противном случае функция вызывает саму себя с аргументом n — 1 и умножает результат на n. Как только n достигает значения 1, рекурсия заканчивается, и функция начинает возвращать значения из рекурсивных вызовов. Это пример рекурсивного алгоритма, потому что он использует вызов функции из самой себя.

5. Вероятностные: использование случайных чисел для решения задач, например с помощью Math.random():

function randomBoolean()

В этом примере функция randomBoolean() генерирует случайное число с помощью метода Math.random(), который возвращает псевдослучайное число между 0 и 1. Затем функция сравнивает это число с 0,5 и возвращает true, если оно меньше 0,5, и false, если оно больше или равно 0,5. Таким образом, функция будет возвращать true и false с равной вероятностью.

Сортировки

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

От чего зависит сложность алгоритма?

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

1. Размера входных данных: сложность алгоритма возрастает с увеличением размера входных данных
2. Времени выполнения: хорошо написанные алгоритмы работают быстрее, чем другие, что влияет на время выполнения
3. Ограничений ресурсов: размер доступной памяти, мощность процессора или место на сервере влияют на результат
4. Наличия вложенных циклов или рекурсивных вызовов: вложенные циклы или рекурсивные вызовы увеличивают количество операций, необходимых для выполнения алгоритма.

Сложность алгоритма измеряется в большой О-нотации (Big-O notation), которая показывает, как быстро растет время выполнения алгоритма при увеличении размера входных данных.

Катрин Алимова

Вам может также понравиться.

Книги для развития Soft Skills

7 янв. 2024 г.

Топ 11 книг как стать эффективнее

4 янв. 2024 г.

Алгоритмы сортировки: что, зачем и почему?

Алгоритмы сортировки: что, зачем и
почему?
• Алгоритм = пошаговая инструкция, которая дополняет код,
прописывается для объяснения значения последнего и
произведения компьютером определенного действия. Чаще всего
применяются алгоритмы сортировки данных. Последние
помогают компьютеру должным образом подойти к работе с
информацией.
• Сортировка данных – это то, что будет преследовать
программиста от начала учебы и до… Но так как она постоянно
нужна и в повседневной жизни, эту подкатегорию алгоритмов
следует бояться меньше всего.

3.

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

4.

• Самые популярные алгоритмы сортировки:
1. Пузырьковая.
2. Перемешиванием.
3. Вставками.
4. Быстрая.
5. Расчёской.
6. Пирамидальная.
7. Выбором.

5.

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

6.

Почему без знания алгоритмов не пройти
собеседование?
• Рекрутер или руководитель, который проводит собеседование
почти всегда дает задачу по алгоритмам на собеседовании. Это
необходимо для оценки знаний базиса. Чаще всего она имеет
условие, где:
1. Специально допущена ошибка, например, предлагается решить
задачу сложным и времязатратным способом, что необходимо
для оценки умения отстаивать свое мнение и внимательно
подходить к задачам.

7.

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

8.

• По факту для сортировки по возрастанию достаточно вызвать
функцию сортировку Python sorted(), которая вернёт новый
отсортированный список:
• Также можно использовать метод список list.sort(), который
изменяет исходный список (и возвращает None во избежание
путаницы). Обычно это не так удобно, как использование sorted(),
но если вам не нужен исходный список, то так будет намного
эффективнее.

9.

• Пример:
• В Python вернуть None и не вернуть ничего — одно и то же.
• Ещё одно отличие заключается в том, что метод list.sort()
определён только для списков, в то время как sorted() работает со
всеми итерируемыми объектами:

10.

11.

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

12.

• Количество итераций внутреннего цикла зависит от номера
итерации внешнего цикла, так как конец списка уже
отсортирован, и выполнять проход по этим элементам смысла нет.
• Пусть имеется список [6, 12, 4, 3, 8].
• За первую итерацию внешнего цикла число 12 переместится в
конец. Для этого потребуется 4 сравнения во внутреннем цикле:

13.

• Результат:
• За вторую итерацию внешнего цикла число 8 переместиться на
предпоследнее место. Для этого потребуется 3 сравнения:

14.

• На третьей итерации внешнего цикла исключаются два последних
элемента. Количество итераций внутреннего цикла равно двум:
• На четвертой итерации внешнего цикла осталось сравнить только
первые два элемента, поэтому количество итераций внутреннего
равно единице:

15.

16.

• Псевдокод пузырьковой сортировки:

17.

• Описание:
• Итак, в псевдокоде мы видим, что мы объявляем функцию с
именем bubble_sort, которая передала единственный объект
списка A.
• Затем мы входим в цикл while, где мы сначала устанавливаем
переменной swapped = false.
• Мы будем использовать эту переменную в конце каждой итерации
цикла while, чтобы посмотреть и проверить – выполнили ли мы
какие-либо замены внутри нашего цикла for. Если нет – мы
выполнили сортировку.
• Цикл for сам увеличивает переменную длины входного списка A.
На каждой итерации цикла for мы проверяем и смотрим, не
отсортированы ли элементы с индексом i и i-1.

18.

• Если это так, мы меняем их местами, и устанавливаем в нашей
переменной swapped значение True. В противном случае мы
переходим к следующей итерации цикла for.
• В первой итерации цикла for мы проверяем элемент с нулевым
индексом на элемент с индексом -1. Мы меняем их местами, если
элемент с нулевым индексом больше, чем элемент с индексом -1.
• После цикла for мы проверяем – выполняем ли мы какие-нибудь
подкачки. (swapped = True).

О сортировках (пузырьковой, быстрой, расческой. )

Эта статья ориентирована в первую очередь на начинающих программистов. О сортировках вообще и об упомянутых в заголовке в интернете море статей, зачем нужно еще одна? Например, есть хорошая статья здесь, на хабре: Пузырьковая сортировка и все-все-все. Во-первых, хорошего много не бывает, во-вторых в этой статье я хочу ответь на вопросы «зачем, что, как, почему».Зачем нужны сортировки? В первую очередь, для поиска и представления данных. Некоторые задачи с неотсортированными данными решить очень трудно, а некоторые просто невозможно. Пример: орфографический словарь, в нем слова отсортированы по алфавиту. Если бы это было не так, то попробуйте найти в нем нужное слово. Телефонная книга, где абоненты отсортированы по алфавиту. Даже если сортировка не обязательна и не сильно нужна, все равно бывает удобнее работать с отсортированными данными.

Вот начальный (неотсортированный) массив:

50

32

40

31

20

30

10

а вот отсортированный:

10

20

32

30

31

40

50

Обратите внимание: порядок элементов 32,31,30 изменился, т.е. сортировка не устойчивая (не стабильная).

Все используемые в статье сортировки сравнивают пару элементов и меняют их, если они не в нужном порядке. Чем же они отличаются? Отличаются способом выбора пар сравниваемых элементов.
Дальше примеры процедур сортировки на языки Си. Везде первый параметр — адрес массива, второй- количество элементов в массиве. Внешний цикл в процедурах назовем проходом, а внутренний — просто циклом.

Простая сортировка

Проход перебирает все элементы массива и в цикле сравнивает текущий элемент со всеми последующими.

void sorto(int *m,int n) // обычная, простая, примитивная. сортировка < int tmp; for (int i=0;i> > > 

Результат работы

10

20

32

31

30

40

50

Плюсы простой сортировки — они простая в реализации и устойчивая.
Минусы — она очень медленная, т.к. происходит очень много операций сравнения. Каждый из n элементов сравнивается со всеми последующими, поэтому количество сравнений ~n*n/2. Если n=100000, то сравнений 5 миллиардов. Правда, если n=1000, то сравнений «только» 500 тыс и современный компьютер может это сделать менее чем за секунду, так что при небольшом количествах это сортировка годится.Ели один важный минус — если данные почти отсортированы (из 100тыс элементов только 10 стоят не на своих местах), то все равно время работы изменится мало, т.к. операций сравнения будет столько же.Попробуем улучшить алгоритм и перейдем к

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

Она же «Bubble» она же «пузырёк.» Внутренний цикл снова и снова пробегает по массиву и сравнивает текущий элемент с предыдущим (поэтому пробег начинается с 1) и если текущий меньше, переставляет его с предыдущим. Место перестановки запоминается в переменной k, и в конце прохода в k находится индекс, начиная с которого массив отсортирован.

void sortb(int *m,int n) < int tmp,k; while(n>1) < // проход проверят, не пора ли заканчивать k=0; // нет перестановок for (int i=1; i> n=k; // с k все отсортировано > > 

В самом худшем случае (когда исходный массив отсортирован в обратном порядке, получается те же n*n/2 сравнений. А в лучшем или в хорошем»? Лучший случай — это когда массив полностью отсоротирован. Тогда на первом проходе ничего переставляться не будет, в конце прохода n присвоится 0 (k=0) и второго прохода не будет. Вместо 100тыс проходов — всего 1! Замечательно, но что, если массив отсортирован, но не совсем. Например переставим в отсортированном массиве минимальный и максимальный элементы и будем сортировать этот «проблемный» массив (помним, что 30-32 имеют одинаковый ключ):

50

20

32

31

30

40

10

На первом шаге 1 прохода «20» сравнивается с «50» и происходит обмен. На следующем шаге «32» сравнивается снова с «50» (он ведь теперь занял место «20». В результате в конце первого прохода «50» займет место в конце, а все остальные сдвинутся на 1 позицию к началу массива. А что произойдет с «10», который был в конце? Он тоже передвинется на 1 позицию к началу. Если представить, что начальные позиции вверху, а конечные внизу, «на дне», то в результате прохода самый тяжелый окажется на дне, а самый легкий «всплывет» на одну позицию. В одной из статей тяжелые элементы называют «зайцам», а легкие — «черепахами». Во время прохода «заяц» быстро бежит в конец (или тонет), пока не встретит более весомого зайца (который примет эстафету и побежит дальше) или пока не займет свое место. А легкие элементы всплывают на одну позицию. Если самый легкий занимает n-ю позицию, то нужно n проходов, чтобы ему добраться до своего места. Самый тяжелый («дробинка») за один проход быстро тонет, а самый легкий («пузырек») -медленно всплывает. Тот пузырек, которому всплывать дольше всех и определяет общее число необходимых проходов. Если самый легкий в конце массива, надо столько проходов, сколько элементов в массиве.

Что же делать с «черепахами», чтобы они не мешали так сильно. На помощь приходит

Шейкерная сортировка

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

Сортировка расчёской

Или гребёнкой. Снова спросим почему пузырек медленно всплывает? Потому что за проход он перемещается на 1 позицию. А почему он перемещается только на 1 позицию? Потому, что сравниваются и переставляются соседние элементы. Так давайте сравнивать не соседние элементы, а находящиеся на расстоянии s (постепенно уменьшая s с каждым проходом). Реализуя эту идею на практике, приходим к сортировке расческой.

void sortc(int *m,int n) < int tmp,k; int s=n; // готовим начальный шаг long long cnt=0; while(n>1) < s/=1.247f; // шаг на этом проходе. На первом проходе получается примерно 80% от размера массива, // и легкие элементы в хвосте переносятся в первые 20% if (s<1) s=1; // 0 быть не может, присвоим 1 k=0; // нет перестановок for (int i=0; i+sm[i+s]/10) < tmp=m[i]; m[i]=m[i+s]; m[i+s]=tmp; k=i; >++cnt; > if (s==1) // шаг 1, как в обычном пузырьке. Включаем контроль n=k+1; > > 

Идея вроде простая и алгоритм не сложный, но результат впечатляет. Сортировка расческой оказывается намного быстрее, чем пузырек/шейкер, она даже может обогнать «быструю» сортировку qsort. Но есть и минус — она не устойчивая (что интуитивно понятно).

Быстрая сортировка qsort

Функция быстрой сортировки нашего массива очень простая:

// компаратор для qsort int fcomp(const void *i, const void *j) < return (*(int *)i)/10 - (*(int *)j)/10; >void sortq(int *m,int n)

Простая оно потому, что использует стандартную быструю сортировку qsort. Посмотрим снова на приведенные алгоритмы. Во всех выбираются и сравниваются пары элементов m[i] и m[j]. Но что такое m[i]? Это i-й элемент в массиве целых чисел m или «элемент, расположенный по адресу Ai=m+i*». Соответственно, j-й элемент расположен по адресу Aj=m+j*. Итак, мы сравниваем элементы по адресами Ai и Aj и переставляем их, если Aj. Этот передается третьим параметром. Хорошо, но как qsort сравнит элементы, ведь у нас хитрый способ сравнения? Она не сравнивает сама, она использует нашу функцию сравнения fcomp, адрес которой передается в 4 параметре. Когда qsort по своему внутреннему алгоритму решит, что надо сравнить i и j-й элементы, она передаст их адреса в качестве 1 и 2 параметров функции fcomp, которая возвращает результат сравнения 0 в зависимости от того, меньше первый параметр второго, равен ему или больше. Если qsort видит, что i0 она просто переставит элементы в массиве (размер элемента она знает, а содержимое ей не важно).

Время сортировки 100001 элемента

Измерим время сортировки для массива, содержащего 100001 элемент на компьютере с процессором Intel i5 (3.3Ггц).Время указано в сек, через дробь указано количество проходов (для быстрой сортировки оно неизвестно).Как и ожидалось, шейкерная сортировка на проблемном массиве (который полностью упорядочен, только первый и последний элементы переставлены) абсолютный лидер. Она идеально «заточена» под эти данные. Но на случайных данных сортировки расческой и qsort не оставляют соперницам шанса. Пузырьковая сортировка на проблемном массиве показывает двукратное увеличение скорости по сравнению с случайным просто потому, что количество операций перестановки на порядки меньше.

Сортировка	Простая	Пузырьковая	Шейкерная	Расчёской	Быстрая (qsort)
Стабильная	+	+	+	—	—
Случайный	23.1/100000	29.1/99585	19.8/50074	0.020/49	0.055
Проблемный	11.5/100000	12.9/100000	0.002/3	0.015/48	0.035
Обратный	18.3/100000	21.1/100000	21.1/100001	0.026/48	0.037

А теперь вернемся к истокам, к пузырьковой сортировке и воочию посмотрим на процесс сортировки. Видите, как на первом проходе тяжелый элемент (50) переносится в конец?

Сравниваемые элементы показаны в зеленых рамках, а переставленные — в красных

Дополнение после публикации

Я ни коей мере не считаю qsort плохой или медленной — она достаточно быстра, функциональна и при возможности следует пользоваться именно ею. Да, ей приходится тратить время на вызов функции сравнения и она уступила «расческе», которая сравнивает «по месту». Это отставание несущественно (сравните с отставанием пузырька от qsort, которое будет увеличиваться при росте массива). Пусть теперь надо сравнивать не числа, а какую-то сложную структуру по определенному полю и пусть эта структура состоит из 1000 байтов. Поместим 100тыс элементов в массив (100мб — это кое-что) и вызовем qsort. Функция fcomp (функция-компаратор) сравнит нужные поля и в результате получится отсортированный массив. При этом при перестановке элементов qsort придется 3 раза копировать фрагменты по 1000 байтов. А теперь «маленькая хитрость» — создадим массив из 100тыс ссылок на исходные элементы и передадим в qsort начало этого массива ссылок. Поскольку ссылка занимает 4 байта (в 64 битных 8), а не 1000, то при обмене ссылок qsort надо поменять эти 4/8 байтов. Разумеется, нужно будет изменить fcomp, поскольку в качестве параметров она теперь получит не адреса элементов, а адреса адресов элементов (но это несложное изменение). Зато теперь можно сделать несколько функций сортировки (каждая сортирует по своему полю структуры). И даже, при необходимости, можно сделать несколько массивов ссылок. Вот сколько возможностей дает qsort!

Кстати: использование ссылок на объекты вместо самих объектов может быть полезно не только при вызове qsort, но и при применении таких контейнеров как vector, set или map.

Количество сравнений и обменов

В следующей таблице показывается количество операций сравнения/количество обменов для каждой сортировки. Для qsort количество обменов неизвестно, поэтому показано только количество сравнений. Видно, что для случайного массива количество сравнений минимально у qsort.

Сортировка	Простая	Пузырьковая	Шейкерная	Расчёской	Быстрая (qsort)
Случайный	5’000’050’000/1’131’715’503	4’999’702’086/2’507’142’238	3’341’739’679/2’507’142’238	4’489’129/714’533	1’915’414
Проблемный	5’000’050’000/199’999	5’000’050’000/199’999	299’997/199’999	4’395’305/91’829	1’588’741
Обратный	5’000’050’000/5’000’050’000	5’000’050’000/5’000’050’000	5’000’050’000/5’000’050’000	4’395’305/233’210	1’588’741

Что такое и зачем нужны алгоритмы

В начале карьеры разработчикам бывает трудно представить, зачем нужны алгоритмы во фронтенде, потому что большинство задач джунов можно решить и без них. Но когда дело доходит до серьёзных задач, грейдов и зарплат, знание алгоритмов выходит на первое место.

Что такое алгоритмы?

Алгоритм — это набор инструкций для решения какой-то задачи. Всё, что мы делаем: готовим утром кофе, идём на работу, пишем код — это исполнение определённых алгоритмов.

У каждого алгоритма есть исполнитель. Например, код, который мы пишем — это набор инструкций, а исполняет его компьютер. Быть исполнителем можете и вы сами, когда занимаетесь любыми повседневными задачами. Например, когда собираетесь на работу:

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

�� Изучите алгоритмы

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

Востребованы ли алгоритмы на рынке фронтенд-разработки?

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

Кроме того, алгоритмы — частые гости на технических собеседованиях на мидловские и сеньорские позиции. Особенно любят добавлять в интервью алгоритмические секции крупные компании вроде Яндекса или Google.

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

• Лишь 2% вакансий с опытом до года требуют знания алгоритмов и структур данных.
• В вакансиях для разработчиков с опытом до шести лет этот навык упоминается в 10% случаев.
• Почти каждая третья вакансия для фронтендеров с опытом более 6 лет содержит этот навык в требованиях к соискателю.

Какие задачи решают с помощью алгоритмов?

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

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

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

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

Сортировка данных

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

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

Сортировка вставкой помогает поддерживать отсортированность в уже существующем массиве при поступлении новых элементов.

При использовании этого метода мы сначала получаем новый элемент, который нужно вставить в массив. Затем проходим по массиву слева направо, пока не встретим элемент, который больше вставляемого. Как только это произойдёт — добавляем новый элемент на нужную позицию.

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

А затем обновляем связи в списке:

Quicksort — одна из самых быстрых сортировок для использования на больших объёмах данных.

Как она работает: сначала мы выбираем в массиве любой «опорный» элемент. Затем сравниваем каждый из элементов с опорным. По результатам сравнений переставляем элементы в массиве так, чтобы слева от опорного были все элементы меньше него, а справа — больше или равны. После этого запускаем этот же алгоритм рекурсивно на левую и правую части массива, пока не придём к массиву из одного элемента.

Посмотрим на сортировку массива из девяти элементов. Сначала выбираем опорный элемент — 5. Затем перемещаем элементы меньше слева от него, а элементы больше — справа.

Теперь берём часть слева и выбираем новый опорный элемент — 3. Затем вновь перемещаем элементы меньше слева от него, а элементы больше — справа. Делаем так, пока полностью не отсортируем левую часть:

Когда закончим, повторим всё то же самое с правой частью:

function quickSort(array, left, right) < left = left ?? 0; right = right ?? array.length - 1; const pivotIndex = partition(array, left, right); logIteration(array, array[pivotIndex], left, right); if (left < pivotIndex - 1) < quickSort(array, left, pivotIndex - 1); >if (pivotIndex < right) < quickSort(array, pivotIndex, right); >return array; > function random(min, max) < const interval = max - min; const shift = min; return Math.round(Math.random() * interval + shift); >function partition(array, left, right) < const pivot = array[random(left, right)]; while (left < right) < while (array[left] < pivot) < left++; >while (array[right] > pivot) < right--; >if (left > return left; > 

Есть множество других видов сортировок. Какой из них использовать — зависит от конкретной задачи.

Поиск в массиве

Найти что-то в массиве — довольно распространённая задача. Это может быть поиск целого объекта по его признаку. Например, когда нам нужно найти объект банковской карточки по id. Или это может быть проверка на вхождение. К примеру, мы можем узнать, разрешено ли показывать определённый контент пользователю. Для этого достаточно проверить его права в массиве прав, разрешающих просмотр.

Линейный поиск — самый распространённый, хотя и медленный, способ поиска в массивах и других коллекциях. Это довольно простой алгоритм, он перебирает все элементы до тех пор, пока не встретит нужный или не дойдёт до конца массива.

Как он работает: к примеру, мы хотим проверить, есть ли слово ‘скрипт’ в массиве [‘веб’, ‘деплой’, ‘сервер’] . Сначала мы посмотрим на ‘веб’ и сравним его с искомым словом. Они не равны, поэтому двигаемся дальше — к слову ‘деплой’ . С ним и ‘сервер’ ситуация такая же: сравнение их со ‘скрипт’ -ом вернёт false . А затем мы придём в конец массива. Это значит, искомого элемента в нём нет.

Проверка на вхождение слова с помощью include :

const words = ['веб', 'деплой', 'сервер']; function checkIfInclude(word) < return words.includes(word); >checkIfInclude('скрипт'); // false 

Если бы мы искали в массиве слово веб , то нашли бы его при сравнении с первым элементом массива и на этом закончили поиск:

Бинарный поиск — поиск, который можно вызывать только на отсортированных массивах данных. Он работает по методу indexOf : принимает элемент, который нужно найти в массиве, и возвращает либо его позицию, либо -1 , либо null .

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

Бинарный поиск удобен для работы с большими отсортированными массивами. Представьте, что вам нужно найти пользователя в базе данных из миллиона человек. Если перебирать каждый элемент последовательно, вы потратите немало времени. Гораздо быстрее и проще сузить поиск, отбросив сразу половину элементов.

Простой пример бинарного поиска:

function binarySearch(numbers, target) < let left = 0; let right = numbers.length - 1; while (left if (numbers[center] > target) < right = center - 1; >else < left = center + 1; >> return null; > 

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

Оптимизация кода

В своей работе мы так или иначе работаем с DOM-деревом. Подбор правильных алгоритмов для работы с деревьями помогает ускорить работу страницы при обработке больших фрагментов дерева.

Переобходить DOM-дерево можно разными способами. Самый простой — поиск в ширину. Он хорошо подходит для поиска, если искомый элемент лежит «сверху» и дерево довольно широкое.

Особенность поиска в ширину в том, что мы сначала просматриваем все элементы на одном уровне вложенности, затем переходим на следующий — и так далее, пока не обойдём всё:

const root = document.body; const resultElement = document.getElementById('result'); function traverse(node) < const result = []; const queue = []; queue.push(node); while(queue.length) < const currentNode = queue.shift(); result.push(currentNode.localName); queue.push(. currentNode.children); >resultElement.innerHTML = result.join(' -> '); > traverse(root); 

Если дерево узкое и элемент находится внизу, подойдёт поиск в глубину. Ниже показан его пример: мы сначала обрабатываем узел, на которой находимся, а затем рекурсивно вызываем операцию обхода на всех потомках.

const root = document.body; const resultElement = document.getElementById('result'); function traverse(node) < const result = []; function recursive(node) < result.push(node.localName); for (const child of node.children) < recursive(child); >> recursive(node); resultElement.innerHTML = result.join(' -> '); > traverse(root); 

Отрисовка динамических списков и парсинг

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

Рекурсия также позволяет справиться с другой распространённой задачей — распарсить текст из HTML-документа без использования регулярных выражений. Например, если у нас есть такой текст:

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

С помощью рекурсии можно быстро перевести его в такой:

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

Всё, что для этого нужно сделать — переобойти DOM, рекурсивно вызывая парсинг.

Добавление данных в очередь

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

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

Мы перечислили лишь небольшую часть задач, которые можно решать с помощью алгоритмов. Но на самом деле их возможности гораздо шире.

Вывод

Алгоритмы — важный инструмент для повышения грейда фронтенд-разработчика. Умение применять их в работе не только помогает быстрее решать типовые задачи, но и открывает возможность трудоустройства на высокооплачиваемые позиции.

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

Один из самых простых способов начать изучение алгоритмов — книги. Начать можно с «Грокаем алгоритмы», в ней Адитья Бхаргава простыми словами пишет о популярных концептах алгоритмостроения, хотя и не всегда применимых к фронтенду. А тем, кто не боится сложного академического языка, советуем прочитать книгу Дональда Кнута «Искусство программирования» о важнейших и базовых алгоритмах, которые мы используем. Можно сказать, что это своего рода «Библия» алгоритмов.

Больше материалов

• Почему разработчики выбирают Vue
• Паттерны проектирования
• Что такое CMS и как под них верстать

«Доктайп» — журнал о фронтенде. Читайте, слушайте и учитесь с нами.