Итак, привет, ребята, меня зовут Куинстон, и сегодня мы собираемся изучить внутреннюю работу Bitonic Sort и код, который ее активирует. Но прежде чем мы перейдем к этому. Спасибо, и приступим.
Bitonic Sort - это алгоритм сортировки на основе параллельного сравнения, который выполняет O (nlogn) сравнений. Это также называется сортировкой слияния Bitonic. Битоническая сортировка основана на концепции преобразования данной последовательности в битовую последовательность. Итак, что же такое Битоническая последовательность?
Битоническая последовательность - это последовательность чисел, которая сначала строго возрастает, а затем, после точки, строго убывает. Итак, значения элементов последовательности растут от начала и уменьшаются к концу. Примером этого может быть последовательность [6, 7, 8, 9, 5, 3, 2, 1]. В этом примере значение элементов увеличивается с [6, 7, 8, 9], а затем уменьшается с [5, 3, 2, 1]. Это почти то же самое, что смотреть на градиент, значение которого увеличивается и уменьшается. Точка, в которой градиент меняет направление, называется битонической точкой. Кроме того, Bitonic Sort работает только с последовательностями, длина которых находится в порядке степени 2, например, 4, 8, 16 и т. Д. Это может быть ограничением, но именно так оно работает.
Последовательность, которая отсортирована в порядке возрастания или в порядке возрастания, также является Bitonic, поскольку убывающая часть последовательности считается пустой. Точно так же в последовательности, которая отсортирована в порядке убывания, или убывающая последовательность также является Bitonic, поскольку возрастающая часть считается пустой. Еще одна важная вещь, о которой следует помнить, - это то, что последовательность при повороте остается битонической. В данном случае вращение - это процесс либо взятия первого элемента последовательности и добавления его в конец последовательности, либо взятия последнего элемента последовательности и его добавления к начальной последовательности. Вращение сохраняет битонический характер последовательности.
Прежде чем изложить шаги алгоритма, есть одна конкретная концепция, о которой вам нужно знать, а именно, какая минимальная возможная битоническая последовательность? Давай подумаем об этом. Исходя из определения битонической последовательности, мы предполагаем, что наименьшая битовая последовательность будет последовательностью из 4 чисел, в которой первые 2 элемента расположены в порядке возрастания, а вторые два элемента - в порядке убывания. Но в этом случае вы совершите серьезную ошибку, потому что вам не нужны ни восходящая, ни нисходящая части для создания битонической последовательности. Чистая восходящая или чистая убывающая последовательность также является битонной последовательностью. А теперь давайте задумаемся глубже. А как насчет двух последовательных номеров? Если у вас два числа подряд, допустим, это 3 и 7. Проще говоря, 3 и 7 образуют восходящую последовательность, поэтому они являются битоническими. Если вы поменяете местами их расположение, то вы получите 7 и 3. Это тоже Bitonic, поскольку это нисходящая последовательность. Итак, реализация состоит в том, что любые два случайных последовательных элемента образуют битовую последовательность.
Давайте рассмотрим пример, чтобы лучше понять, как это работает. Итак, рассмотрим последовательность…
[ 3, 7, 4, 8, 6, 2, 1, 5 ]
Итак, это была самая распространенная последовательность, которая используется повсюду в Интернете для иллюстрации Bitonic Sort, поэтому я подумал, что было бы неплохо использовать ее.
Исходя из принципа, который мы реализовали ранее, с размером последовательности 8, где сейчас существуют 4 последовательности Bitonic. А именно: 3 и 7, 4 и 8, 6 и 2 и 1 и 5. Размер текущих Bitonic Sequences равен 2. Нам не нужно было выполнять никаких операций, чтобы добраться до этого этапа. Отсюда мы начинаем выполнение алгоритма.
Первый шаг - выяснить, каков размер битонической последовательности, которую нам нужно сформировать в текущей последовательности. Мы получаем это, удваивая размер существующей Bitonic Sequence. Размер существующей Bitonic Sequence равен 2. Удвоив его, мы получаем 4. Итак, размер Bitonic Sequence, который нам нужно сформировать, равен 4.
Последовательность состоит из 8 элементов. Отсюда мы рассматриваем 4 элемента каждый и создаем 2 группы. Теперь мы перейдем к преобразованию каждой из этих групп в битонные последовательности. В конце этого цикла у нас будет 2 битонных последовательности в нашей основной последовательности. Итак, как нам от этих последовательностей? Здесь мы используем 2 инструмента, а именно: расстояние и направление сравнения.
Расстояние для сравнения - это расстояние между элементами, которые вы собираетесь сравнивать, а направление - это порядок, в котором вы хотите расположить значения. Если элементы не расположены в правильном порядке синхронно с направлением, эти элементы нужно поменять местами. Направление указано стрелкой, а расстояние - длиной стрелки. Давайте углубимся в пример, чтобы увидеть, как это реализовано.
Первая группа содержит элементы, [3, 7, 4, 8]. Мы должны преобразовать это в битоническую последовательность. Теперь нам нужно найти расстояние сравнения. Расстояние обычно составляет половину размера существующей Bitonic Sequence. В нашем случае длина Bitonic Sequence, которая у нас сейчас есть, равна 2, а половина 2 равна 1. Итак, мы должны сравнить элементы, которые находятся на расстоянии 1 друг от друга в группе. Поскольку эта группа должна быть преобразована в битовую последовательность, первая часть последовательности должна увеличиваться, а следующая часть последовательности должна уменьшаться. Чтобы упростить работу нашего мозга, мы разделили группу на 2 равные части. Первая часть содержит элементы 3 и 7, а вторая часть содержит элементы 4 и 8.
Теперь мы должны нарисовать стрелки, чтобы обозначить, какие элементы сравнивать и в каком направлении они должны увеличиваться и уменьшаться. Расстояние для сравнения равно 1. Начнем с 3 и рисуем стрелку длиной 1 слева направо. Поскольку эта часть группы должна располагаться в порядке возрастания, стрелка указывает слева направо. Мы могли бы подумать, что следующую стрелку нужно будет нарисовать из 7, но нет. Предыдущая стрелка заканчивается на 7, так что 7 уже является частью сравнения. Множественное сравнение не может выполняться одновременно для одних и тех же элементов. Следующая стрелка будет нарисована из 4 с расстоянием 1. Предполагается, что эта часть группы находится в порядке убывания, следовательно, направление стрелки будет справа налево.
Аналогично во второй группе [6, 2, 1, 5]. Мы повторяем тот же процесс. Рисование стрелок от 6 с расстоянием 1, указывающее слева направо, и рисование стрелок от 1 с расстоянием 1, указывающее справа налево. Теперь пора либо поменять местами, либо сохранить положение элементов.
3 и 7 расположены в правильном порядке увеличения значения, поскольку они синхронизированы с направлением стрелки, следовательно, их положения сохраняются. 4 и 8 расположены в неправильном порядке, поэтому их необходимо поменять местами. 6 и 2 находятся в неправильном направлении, поэтому их необходимо поменять местами. 1 и 5 также находятся в неправильном направлении, поэтому их нужно поменять местами. Эти операции дают нам последовательность, [3, 7, 8, 4, 2, 6, 5, 1]. Это конец первого этапа.
Bitonic Sort состоит из этапов и проходов. Проходы - это подмножество этапов. Смена этапа - это переход от формирования битонической последовательности меньшего размера к более крупной битонической последовательности. Смена прохода - это когда вы начинаете рекурсивно сравнивать элементы в той же группе на расстоянии, равном половине предыдущего. Давайте перейдем к следующему этапу, чтобы глубже понять это.
Этап 2 включает продвижение вверх для формирования более крупной битонической последовательности. Bitonic Sequence, который нам нужно сформировать при переходе на новый этап, в два раза превышает размер существующей Bitonic Sequence. Существующая битовая последовательность имеет длину 4, поэтому следующая битовая последовательность должна иметь размер 8. Вся текущая последовательность состоит из 8 элементов. Таким образом, нам не нужно создавать какие-либо группы и нужно преобразовывать всю последовательность в битовую последовательность. Следующим шагом в алгоритме является вычисление расстояния сравнения. Расстояние сравнения, опять же, составляет половину длины существующей Bitonic Sequence. Длина существующей Bitonic Sequence, опять же, равна 4, поэтому расстояние для сравнения равно 2, поскольку 2 равно половине 4. Нарисуем стрелки. Поскольку Bitonic Sequence, который нам нужно сформировать, имеет длину 8, предполагается, что первые 4 элемента находятся в порядке возрастания, а следующие 4 элемента - в порядке убывания.
Итак, мы начинаем с рисования стрелки от первого элемента, который равен 3. Стрелка имеет длину 2, поэтому заканчивается на 8. Предполагается, что эта часть последовательности находится в возрастающем порядке, поэтому стрелка указывает слева направо. . Затем мы рисуем стрелку из следующего элемента, то есть 7. Стрелка заканчивается на 4 и имеет длину 2. И снова стрелка указывает слева направо. Можно было бы предположить, что следующая стрелка будет от 8, но нет. Вы не можете нарисовать стрелку из 8, поскольку элемент уже является частью операции, которая еще не завершена. Кроме того, еще одна причина заключается в том, что если вы нарисуете стрелку из 8 с длиной 2, она войдет в убывающую часть, что недопустимо. Перекрестное опыление или, более конкретно, перекрестное сравнение и обмен не разрешены. Это две разные порции, и обращаться с ними нужно именно так. Точно так же мы не можем нарисовать стрелку из 4, не придерживаясь правил, о которых мы только что говорили.
Итак, переходя к следующей части последовательности, мы рисуем стрелку от 2 до 5. Эта стрелка указывает справа налево, поскольку эту часть необходимо расположить в порядке убывания. Точно так же стрелка рисуется от 1 до 6, которая указывает справа налево. Теперь выполняй.
7 заменяется на 4, а 2 заменяется на 5, потому что они находятся в неправильном направлении. На предыдущем этапе мы остановились здесь и перешли к следующему этапу. Но мы не можем сделать это здесь, поскольку последовательность, которую мы только что получили, не является Bitonic. Нам нужно завершить все проходы на этом этапе, чтобы получить полностью битоническую последовательность. Итак, как нам перейти на новый проход на этом этапе? Разделите текущее расстояние сравнения на 2 и повторите процесс. Давайте сделаем это.
Текущее расстояние сравнения равно 2, поэтому, если мы вдвое меньше, мы получим 1. Итак, давайте нарисуем стрелки длиной 1 в наших существующих частях группы в порядке возрастания и убывания. Стрелка попадает из 3 длины 1 слева направо. Мы не можем нарисовать стрелку из 4, поскольку это часть операции, которая еще не завершена. Рисуем стрелку из 8 длиной 1 слева направо. Точно так же стрелка, указывающая справа налево от 5 длины 1, и стрелка, указывающая справа налево 2 длины 1. Давайте выполним.
8 заменяется на 7, а 5 заменяется на 6, чтобы переставить значения в правильном порядке. Мы хотели бы перейти к следующему проходу на этом этапе, но когда мы половину расстояния сравнения, мы получаем длину 0,5, которая сводится к нулю. Никаких элементов не существует на расстоянии 0,5 или 0 друг от друга. Таким образом, это конец этого этапа, и мы получаем последовательность [3, 4, 7, 8, 6, 5, 2, 1]. Если подумать, причина того, что у нас не было еще одного прохода на первом этапе, заключалась в том, что начальное расстояние сравнения было 1, поэтому не было причин для другого прохода.
Переходя к следующему этапу, нам нужно найти размер битонической последовательности, которую нам нужно сформировать. Размер существующей Битонической Последовательности равен 8, поэтому длина следующей Битонической Последовательности будет вдвое больше 8, что составляет 16. Но вы можете подумать… подождите. Размер всей последовательности равен 8. Как мы можем сделать битонную последовательность размером 16. Ответ - нет. Вы просто делаете вид, что создаете Bitonic Sequence размера 16, и в процессе вы сортируете текущий размер Bitonic Sequence 8. Насколько это безумие? Просто подумай об этом немного. Это безумие.
Давайте перейдем к первому этапу этого этапа. Наше начальное расстояние сравнения составляет половину размера текущей Bitonic Sequence. Текущая битовая последовательность имеет размер 8, поэтому расстояние для сравнения - размер 4. Мы формируем битовую последовательность размером 16, поэтому первые 8 элементов будут в порядке возрастания, а следующие 8 элементов, ну, они не существует. Но если бы они это сделали, они были бы в порядке убывания. Нарисуем стрелки.
Стрелки идут слева направо от 3 до 6, от 4 до 5, от 7 до 2 и от 8 до 1. 7 заменяется на 2, а 8 заменяется на 1 для сохранения правильного направления. При переходе к следующему проходу расстояние сравнения становится половиной от 4, то есть 2. Стрелка рисуется от 3 к 2, 4 к 1, 6 к 7 и 5 к 8. Все стрелки расположены слева направо. 3 заменяется на 2, а 4 заменяется на 1.
Для следующего прохода расстояние сравнения уменьшается вдвое, поэтому оно становится 1 из 2. Стрелки, указывающие слева направо, рисуются от 2 до 1, от 3 до 4, 6 до 5 и 7 до 8. 2 заменяется на 1, 3 меняются местами. с 4 и 6 заменяется на 5. Мы не можем перейти к следующему проходу, так как уменьшение расстояния вдвое даст нам значение меньше 1. Это конец текущего этапа. В итоге мы получаем последовательность [1, 2, 3, 4, 5, 6, 7, 8].
Последовательность отсортирована, как вы можете ясно видеть. Вот как на самом деле работает Bitonic Sort.
Вы можете найти полностью прокомментированный код на моем Github.
Изучите Как создать побочный SaaS-сервис, который действительно приносит деньги - для программистов и хакеров, которые могут создавать программное обеспечение самостоятельно.
Используйте код купона «launch30», чтобы получить скидку 30%.
Я также делаю забавные увлекательные видео о структурах данных и алгоритмах на YouTube. Я уверен, что они принесут вам большую пользу на вашем пути к тому, чтобы стать элитным программистом. Найдите ссылку на канал здесь.
