Структуры данных и алгоритмы Python: создание программы для битонической сортировки

Поиск и сортировка в Python: упражнение 11 с решением

Напишите код Python для создания программы для Битонической сортировки.
Битоновая сортировка: согласно rutgers.edu - Битоновая сортировка - это алгоритм сортировки, основанный на сравнении, который может выполняться параллельно. Основное внимание уделяется преобразованию случайной последовательности чисел в битонную последовательность, которая монотонно увеличивается, а затем уменьшается. Вращения битовой последовательности также являются битонными.
Более конкретно, битоническая сортировка может быть смоделирована как тип сети сортировки. Исходная несортированная последовательность поступает через входные каналы, где ряды компараторов переключают две записи в порядке возрастания или убывания.
Алгоритм, созданный Кеном Бэтчером в 1968 году, состоит из двух частей. Во-первых, несортированная последовательность встроена в битовую последовательность; затем серия разбивается несколько раз на более мелкие последовательности, пока входные данные не будут отсортированы.

Пример решения :

Код Python:

License:  https://bit.ly/2InTS3W 
# Python program for Bitonic Sort. Note that this program 
# works only when size of input is a power of 2. 
# The parameter dir indicates the sorting direction, ASCENDING 
# or DESCENDING; if (a[i] > a[j]) agrees with the direction, 
# then a[i] and a[j] are interchanged.*/ 
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]
        # It recursively sorts a bitonic sequence in ascending order,
# if dir = 1, and in descending order otherwise (means dir=0).
# The sequence to be sorted starts at index position low, 
# the parameter cnt is the number of elements to be sorted. 
def bitonicMerge(a, low, cnt, dire):
    if cnt > 1:
        k = int(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)
        # This funcion first produces a bitonic sequence by recursively
# sorting its two halves in opposite sorting orders, and then
# calls bitonicMerge to make them in the same order 
def bitonicSort(a, low, cnt, dire):
    if cnt > 1:
        k = int(cnt / 2)
        bitonicSort(a, low, k, 1)
        bitonicSort(a, low + k, k, 0)
        bitonicMerge(a, low, cnt, dire)
        # Caller of bitonicSort for sorting the entire array of length N
# in ASCENDING order
def sort(a, N, up):
    bitonicSort(a, 0, N, up)
# Driver code to test above
a = []
print("How many numbers u want to enter?");
n = int(input())
print("Input the numbers:");
for i in range(n):
    a.append(int(input()))
up = 1
sort(a, n, up)
print("\n\nSorted array is:")
for i in range(n):
    print("%d" % a[i])

Пример вывода:

 Сколько номеров вы хотите ввести?
 5
Введите цифры:
 25
 13
 76
 59
 37
Сортированный массив:
13
25
59
76
37

Блок - схема:

Редактор кода Python:

Внесите свой код и комментарии через Disqus.

Предыдущая: Написать программу на Python Программа для подсчета сортировки.
Далее: Напишите программу на Python для сортировки списка элементов, используя сортировку Bogosort.