Простое объяснение наиболее распространенных алгоритмов сортировки и поиска на одном простом примере.

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

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

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

Алгоритмы сортировки

Представьте, что вы находитесь в комнате с несколькими другими людьми. И кто-то просит вас выстроить всех этих людей. Что бы вы сделали? Как бы вы выполнили эту задачу?

Вы можете использовать несколько разных подходов. Эти подходы обычно называют алгоритмами сортировки, потому что все, что вам нужно сделать, это отсортировать этих людей от самых коротких (слева) до самых высоких (справа). А теперь я собираюсь объяснить наиболее распространенные алгоритмы сортировки с помощью этой метафоры «люди в одной строке».

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

Допустим, наши люди уже выстроились в очередь, но без всякого порядка. Самое простое (на мой взгляд), что мы можем сделать, это сравнить первых двух человек и поменяться местами, если второй меньше первого. Затем мы берем третьего человека и сравниваем его со вторым. Если третье меньше второго, то меняем их местами. А если он меньше первого - тоже меняем местами. Если наш третий человек не меньше второго или первого - мы оставляем его там, где он был, потому что это означает, что он уже на своем месте.

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

В псевдокоде мы можем написать решение следующим образом:

for each person in a line:
    for each person before him:
        if he is smaller:
            swap them

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

2. Сортировка выбора

Этот метод улучшает пузырьковую сортировку. Теперь нам не нужно сравнивать каждого человека со всеми его соседями. Вместо этого на каждой итерации нам просто нужно найти самого маленького (или самого высокого) человека в толпе.

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

В псевдокоде наша программа будет выглядеть так:

for all the people in the line:
    find the smallest person
    put him after the person we choose on previous step
        (if he is the first - just put him on the most left edge)
    remove him from the consideration

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

3. Сортировка вставки

Очень похоже на предыдущий метод, но теперь мы не выбираем самого маленького (или самого высокого) человека. Мы берем первого встреченного нами человека и помещаем его в самое начало.

Затем мы берем другого человека и сравниваем его с первым. Если он выше первого - ставим на второе место. В противном случае ставим его на первое место, а того, кто был первым, перемещаем на второе.

Мы продолжаем делать это со всеми остальными: занимаем свое место в очереди, перемещая тех, кто выше, вправо, если это необходимо.

Программа в псевдокоде может выглядеть так:

take the first person and put him on the first place
for all the rest of the people:
    compare each one with the people who are already in the line
    find his place moving those who are taller to the right

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

4. Сортировка слиянием

Что, если мы хотим повысить эффективность процесса? Мы должны изобрести что-то новое. И ответ на этот вызов - разделение людей на группы. На небольшие группы, очень маленькие группы. Мы делим их на группы по одному человеку в каждой. Звучит действительно странно.

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

В псевдокоде мы можем записать эту логику следующим образом:

while the number of people in a group bigger then 1:
    divide the group in halves
    do this process to the left half of people
    do this process to the right half of people
    combine two groups of people:
        if the next person in the first group is taller:
            put him in the next place of combined group
        else:
            put there the next person from another group

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

Но у этого подхода есть и недостаток: для этого требуется дополнительная память.

5. Быстрая сортировка

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

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

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

Продолжаем процесс до тех пор, пока не найдется один человек в каждой группе. Значит, мы отсортировали строку от начала до конца.

Мы можем написать это в псевдокоде:

take the first person as a model
for each person from the left edge and from the right edge:
    if someone from the left side is taller than the model
    and if someone from the right side is smaller than the model:
    swap them
continue doing this until the left side will meet the right side
move the model to the point where the left side met the right side
repeat the process for the left and right parts from the model
do this until there will be one person in each part

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

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

Хорошо, теперь мы знаем, как сортировать людей, например поставьте их в ряд от самого маленького до самого высокого. Но что, если мы хотим найти в этой комнате человека точно такого же роста, как и вы? Что нам делать? Как нам его найти? Мы можем использовать один из алгоритмов поиска, который я хочу сейчас описать.

1. Последовательный поиск

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

В псевдокоде мы сделаем это так:

for each person in the room:
    compare me with him
    if we are the same heighth:
        I've found my vis-a-vis
        the task completed

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

2. Поиск в прыжке

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

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

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

devide people into small groups
(usually the number of people in each group defines as the square root of the number of all the people)
for number of groups:
    compare yourself with the first person in each group
    until you'll find someone taller than you
for each person in previous group:
    compare yourself with every person in a group
    until you either find someone you need - success!
    or not - failure

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

3. Бинарный поиск

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

Еще нужно найти в комнате человека вашего роста. Но теперь вы подходите к человеку точно в середине очереди и сравниваете себя с ним. Если выше ростом - вправо, меньше - влево. Снова сравните себя с человеком в середине этой половины. И так до тех пор, пока вы либо не найдете кого-то своего роста, либо не поймете, что в этой комнате нет никого, кто был бы на столько сантиметров, как вы.

В псевдокоде этот процесс можно записать следующим образом:

while there are people in the group:
    find the middle person of a group
    if you are bigger:
        goupe = half of a group to the right side
    if you are smaller:
        group = half of a group to the left side
    if you are the same height:
        he is found
        the tast is done

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

Это краткий обзор наиболее простых и распространенных алгоритмов программирования сортировки и поиска. К каждому объяснению я приводил примеры в псевдокоде. Я сделал это с определенной целью. Не так важно, какой язык программирования вы используете для написания этих алгоритмов. Самое главное - вы их понимаете? Если да, вы можете написать его на любом языке. И я надеюсь, что с этой метафорой людей вы приблизились к пониманию. Если так, то я счастлив, потому что это была моя цель.