Рубрики

Java программа для сортировки по битону

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

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

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

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

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

  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. Поскольку все эти битовые последовательности отсортированы и каждая битовая последовательность имеет один элемент, мы получаем отсортированный массив.

/ * 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);

    }

}

Выход:

Sorted array
1 2 3 4 5 6 7 8

Пожалуйста, обратитесь к полной статье о Битонической сортировке для более подробной информации!

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

Java программа для сортировки по битону

0.00 (0%) 0 votes