Рубрики

Программа Python для Битонической Сортировки

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

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

питон

# Программа 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]),

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

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

Программа Python для Битонической Сортировки

0.00 (0%) 0 votes