Рубрики

Битоновая сортировка

Фон

Bitonic Sort — это классический параллельный алгоритм сортировки.

  • Битонная сортировка выполняет O (n Log 2 n) сравнений.
  • Количество сравнений, выполненных с помощью Битонической сортировки, больше, чем у популярных алгоритмов сортировки, таких как Сортировка слиянием [делает сравнения O (nLogn)], но сортировка по Битонику лучше для параллельной реализации, потому что мы всегда сравниваем элементы в предопределенной последовательности, а последовательность сравнения не зависит от данных. Поэтому он подходит для реализации в аппаратном и параллельном массиве процессоров .

Чтобы понять Битоническую сортировку, мы должны сначала понять, что такое Битоновая последовательность и как сделать данную последовательность битовой.

Битонная последовательность

Последовательность называется битонической, если она сначала увеличивается, а затем уменьшается. Другими словами, массив arr [0..ni] является битоническим, если существует индекс i, где 0 <= i <= n-1, такой, что

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

Как сформировать битонную последовательность из случайного ввода?
Мы начинаем с формирования 4-элементных битонных последовательностей из последовательной 2-элементной последовательности. Рассмотрим 4-элемент в последовательности x0, x1, x2, x3. Мы сортируем x0 и x1 по возрастанию, а x2 и x3 по убыванию. Затем мы объединяем две пары, чтобы сформировать 4-битную битонную последовательность.
Далее мы берем две 4-битные битовые последовательности элементов, сортируя одну в порядке возрастания, другую в порядке убывания (используя битоническую сортировку, о которой мы поговорим ниже) и так далее, пока не получим битонную последовательность.

Пример:
Преобразовать следующую последовательность в битовую последовательность: 3, 7, 4, 8, 6, 2, 1, 5

Шаг 1 : Рассмотрите каждый 2-х последовательных элементов как битонную последовательность и примените битовую сортировку к каждому 2-парному элементу. На следующем шаге возьмем две 4-битные битовые последовательности и так далее.

Примечание: x0 и x1 сортируются в порядке возрастания, а x2 и x3 — в порядке убывания и т. Д.

Шаг 2: Две 4-элементные битовые последовательности: A (3,7,8,4) и B (2,6,5,1) с длиной компаратора 2

После этого шага мы получим битонную последовательность длиной 8.

 3, 4, 7, 8, 6, 5, 2, 1 

Битоновая сортировка

В основном это два шага.

  1. Формирование битовой последовательности (подробно рассмотрено выше). После этого шага мы достигаем четвертой стадии в диаграмме ниже, то есть массив становится {3, 4, 7, 8, 6, 5, 2, 1}
  2. Создание одной отсортированной последовательности из битовой последовательности: после первого шага первая половина сортируется по возрастанию, а вторая — по убыванию.
    Мы сравниваем первый элемент первой половины с первым элементом второй половины, затем второй элемент первой половины со вторым элементом второй и так далее. Мы обмениваемся элементами, если элемент первой половины меньше.
    После вышеупомянутых шагов сравнения и обмена мы получаем две битовые последовательности в массиве. Смотрите пятую стадию в диаграмме ниже. На пятой стадии имеем {3, 4, 2, 1, 6, 5, 7, 8}. Если мы более внимательно посмотрим на элементы, мы можем заметить, что есть две битовые последовательности длиной n / 2, так что все элементы в первой битновой последовательности {3, 4, 2, 1} меньше, чем все элементы второй битонной последовательности {6, 5, 7, 8}.
    Мы повторяем один и тот же процесс в двух битонных последовательностях и получаем четыре битонных последовательности длиной n / 4, так что все элементы самой левой битовой последовательности меньше, а все элементы — самой правой. Смотрите шестую стадию в диаграмме ниже, массивы {2, 1, 3, 4, 6, 5, 7, 8}.
    Если мы повторим этот процесс еще раз, мы получим 8 битовых последовательностей размером n / 8, равным 1. Поскольку все эти битовые последовательности отсортированы и каждая битовая последовательность имеет один элемент, мы получаем отсортированный массив.

Ниже приведены реализации Bitonic Sort.

C ++

/ * C ++ Программа для Битонической Сортировки. Обратите внимание, что эта программа

   работает только тогда, когда размер ввода равен степени 2 *.

#include<bits/stdc++.h>

using namespace std;

  
/ * Параметр dir указывает направление сортировки, ASCENDING

   или по убыванию; если (a [i]> a [j]) согласуется с направлением,

   тогда a [i] и a [j] взаимозаменяемы. * /

void compAndSwap(int a[], int i, int j, int dir)

{

    if (dir==(a[i]>a[j]))

        swap(a[i],a[j]);

}

  
/ * Рекурсивно сортирует битоническую последовательность в порядке возрастания,

  если dir = 1, и в порядке убывания в противном случае (означает dir = 0).

  Последовательность для сортировки начинается с позиции индекса низкого уровня,

  параметр cnt - это количество элементов для сортировки. * /

void bitonicMerge(int a[], int low, int cnt, int dir)

{

    if (cnt>1)

    {

        int k = cnt/2;

        for (int i=low; i<low+k; i++)

            compAndSwap(a, i, i+k, dir);

        bitonicMerge(a, low, k, dir);

        bitonicMerge(a, low+k, k, dir);

    }

}

  
/ * Эта функция сначала создает битонную последовательность рекурсивно

    сортировка его двух половинок в противоположных порядках сортировки, а затем

    вызывает bitonicMerge, чтобы сделать их в том же порядке * /

void bitonicSort(int a[],int low, int cnt, int dir)

{

    if (cnt>1)

    {

        int k = cnt/2;

  

        // сортировка в порядке возрастания, так как dir здесь равен 1

        bitonicSort(a, low, k, 1);

  

        // сортировка по убыванию, так как dir здесь 0

        bitonicSort(a, low+k, k, 0);

  

        // Будем объединять последовательность в порядке возрастания

        // так как dir = 1.

        bitonicMerge(a,low, cnt, dir);

    }

}

  
/ * Вызывающая сторона bitonicSort для сортировки всего массива

   длина N в порядке возрастания * /

void sort(int a[], int N, int up)

{

    bitonicSort(a,0, N, up);

}

  
// Код драйвера

int main()

{

    int a[]= {3, 7, 4, 8, 6, 2, 1, 5};

    int N = sizeof(a)/sizeof(a[0]);

  

    int up = 1;   // означает сортировку в порядке возрастания

    sort(a, N, up);

  

    printf("Sorted array: \n");

    for (int i=0; i<N; i++)

        printf("%d ", a[i]);

    return 0;

}

Джава

/ * Java-программа для Битонической сортировки. Обратите внимание, что эта программа

   работает только тогда, когда размер ввода равен степени 2 *.

public class BitonicSort

{

    / * Параметр dir указывает направление сортировки,

       Восходящий или нисходящий; если (a [i]> a [j]) согласен

       с направлением, то a [i] и a [j]

       взаимозаменяемыми. * /

    void compAndSwap(int a[], int i, int j, int dir)

    {

        if ( (a[i] > a[j] && dir == 1) ||

             (a[i] < a[j] && dir == 0))

        {

            // Замена элементов

            int temp = a[i];

            a[i] = a[j];

            a[j] = temp;

        }

    }

  

    / * Рекурсивно сортирует битоническую последовательность по возрастанию

       порядок, если dir = 1, и в порядке убывания

       (означает dir = 0). Последовательность для сортировки начинается с

       позиция индекса низкая, параметр cnt является числом

       элементов для сортировки. * /

    void bitonicMerge(int a[], int low, int cnt, int dir)

    {

        if (cnt>1)

        {

            int k = cnt/2;

            for (int i=low; i<low+k; i++)

                compAndSwap(a,i, i+k, dir);

            bitonicMerge(a,low, k, dir);

            bitonicMerge(a,low+k, k, dir);

        }

    }

  

    / * Эта функция сначала создает битонную последовательность

       рекурсивная сортировка двух половинок в противоположной сортировке

       заказы, а затем вызывает bitonicMerge, чтобы сделать их в

       тот же порядок * /

    void bitonicSort(int a[], int low, int cnt, int dir)

    {

        if (cnt>1)

        {

            int k = cnt/2;

  

            // сортировка в порядке возрастания, так как dir здесь равен 1

            bitonicSort(a, low, k, 1);

  

            // сортировка по убыванию, так как dir здесь 0

            bitonicSort(a,low+k, k, 0);

  

            // Будем объединять последовательность в порядке возрастания

            // так как dir = 1.

            bitonicMerge(a, low, cnt, dir);

        }

    }

  

    / * Вызывающая функция bitonicSort для сортировки всего массива

      длины N в порядке возрастания * /

    void sort(int a[], int N, int up)

    {

        bitonicSort(a, 0, N, up);

    }

  

    / * Утилита для печати массива размером n * /

    static void printArray(int arr[])

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        int a[] = {3, 7, 4, 8, 6, 2, 1, 5};

        int up = 1;

        BitonicSort ob = new BitonicSort();

        ob.sort(a, a.length,up);

        System.out.println("\nSorted array");

        printArray(a);

    }

}

питон

# Программа Python для Битонической сортировки. Обратите внимание, что эта программа
# работает только тогда, когда размер ввода равен степени 2.

  
# Параметр dir указывает направление сортировки, ASCENDING
# или по убыванию; если (a [i]> a [j]) согласуется с направлением,
# тогда a [i] и a [j] взаимозаменяемы. * /

def compAndSwap(a, i, j, dire):

    if (dire==1 and a[i] > a[j]) or (dire==0 and a[i] < a[j]):

        a[i],a[j] = a[j],a[i]

  
# Рекурсивно сортирует битовую последовательность в порядке возрастания,
# если dir = 1, а в порядке убывания (означает dir = 0).
# Последовательность для сортировки начинается с позиции индекса низкого уровня,
# параметр cnt - количество элементов для сортировки.

def bitonicMerge(a, low, cnt, dire):

    if cnt > 1:

        k = cnt/2

        for i in range(low , low+k):

            compAndSwap(a, i, i+k, dire)

        bitonicMerge(a, low, k, dire)

        bitonicMerge(a, low+k, k, dire)

  
# Эта функция сначала создает битонную последовательность рекурсивно
# сортировка двух половинок в противоположных порядках сортировки, а затем
# вызывает bitonicMerge, чтобы сделать их в том же порядке

def bitonicSort(a, low, cnt,dire):

    if cnt > 1:

          k = cnt/2

          bitonicSort(a, low, k, 1)

          bitonicSort(a, low+k, k, 0)

          bitonicMerge(a, low, cnt, dire)

  
# Вызывающая сторона bitonicSort для сортировки всего массива длины N
# в порядке возрастания

def sort(a,N, up):

    bitonicSort(a,0, N, up)

  
# Код драйвера для проверки выше

a = [3, 7, 4, 8, 6, 2, 1, 5]

n = len(a)

up = 1

  
sort(a, n, up)

print ("\n\nSorted array is")

for i in range(n):

    print("%d" %a[i]),

C #

/ * C # Программа для Битонической Сортировки. Обратите внимание, что эта программа

   работает только тогда, когда размер ввода равен степени 2 *.

using System; 

    
/ * Параметр dir указывает направление сортировки, ASCENDING

   или по убыванию; если (a [i]> a [j]) согласуется с направлением,

   тогда a [i] и a [j] взаимозаменяемы. * /

class GFG 

    / * Чтобы поменять значения * /

    static void Swap<T>(ref T lhs, ref T rhs)

    {

        T temp;

        temp = lhs;

        lhs = rhs;

        rhs = temp;

    }

    public static void compAndSwap(int[] a, int i, int j, int dir) 

    

        int k;

        if((a[i]>a[j]))

            k=1;

        else

            k=0;

        if (dir==k)

            Swap(ref a[i],ref a[j]); 

    

        

    / * Рекурсивно сортирует битоническую последовательность в порядке возрастания,

      если dir = 1, и в порядке убывания в противном случае (означает dir = 0).

      Последовательность для сортировки начинается с позиции индекса низкого уровня,

      параметр cnt - это количество элементов для сортировки. * /

    public static void bitonicMerge(int[] a, int low, int cnt, int dir) 

    

        if (cnt>1) 

        

            int k = cnt/2; 

            for (int i=low; i<low+k; i++) 

                compAndSwap(a, i, i+k, dir); 

            bitonicMerge(a, low, k, dir); 

            bitonicMerge(a, low+k, k, dir); 

        

    

        

    / * Эта функция сначала создает битонную последовательность рекурсивно

        сортировка его двух половинок в противоположных порядках сортировки, а затем

        вызывает bitonicMerge, чтобы сделать их в том же порядке * /

    public static void bitonicSort(int[] a,int low, int cnt, int dir) 

    

        if (cnt>1) 

        

            int k = cnt/2; 

        

            // сортировка в порядке возрастания, так как dir здесь равен 1

            bitonicSort(a, low, k, 1); 

        

            // сортировка по убыванию, так как dir здесь 0

            bitonicSort(a, low+k, k, 0); 

        

            // Будем объединять последовательность в порядке возрастания

            // так как dir = 1.

            bitonicMerge(a,low, cnt, dir); 

        

    

        

    / * Вызывающая сторона bitonicSort для сортировки всего массива

       длина N в порядке возрастания * /

    public static void sort(int[] a, int N, int up) 

    

        bitonicSort(a,0, N, up); 

    

        

    // Код драйвера

    static void Main() 

    

        int[] a= {3, 7, 4, 8, 6, 2, 1, 5}; 

        int N = a.Length; 

        

        int up = 1;   // означает сортировку в порядке возрастания

        sort(a, N, up); 

        

        Console.Write("Sorted array: \n"); 

        for (int i=0; i<N; i++) 

            Console.Write(a[i] + " "); 

        }

        // Этот код предоставлен DrRoot_

}


Выход:

 Сортированный массив: 
1 2 3 4 5 6 7 8 

Анализ Битонного Сорта

Чтобы сформировать отсортированную последовательность длины n из двух отсортированных последовательностей длины n / 2, требуются сравнения log (n) (например, log (8) = 3 при размере последовательности. Следовательно, количество сравнений T (n) составляет вся сортировка дается:

T (n) = log (n) + T (n / 2)

Решение этого рекуррентного уравнения

T (n) = log (n) + log (n) -1 + log (n) -2 +… + 1 = log (n) · (log (n) +1) / 2

Так как каждая ступень сортировочной сети состоит из n / 2 компараторов. Поэтому итого? (N log 2 n) компараторов.

Ссылки:
1. https://www.youtube.com/watch?v=GEQ8y26blEY
2. http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
3. https://en.wikipedia.org/wiki/Bitonic_sorter

Эта статья предоставлена Рахулом Агарвалом. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Битоновая сортировка

0.00 (0%) 0 votes