Py学习  »  Python

排序算法 | 双调排序(Bitonic sort)详解与Python实现

机器学习算法与Python学习 • 2 年前 • 354 次点击  




点击 机器学习算 法与Python学习 选择加星标

精彩内容不迷路


本篇为排序算法系列第二篇,详细讲述双调排序算法。


01 什么是双调排序(Bitonic sort)?

上篇提到的珠排序(排序算法 | 珠排序(bead sort)详解与Python实现)是一种自然排序方法,本文介绍的双调排序则属于排序网络(sort net)的一种,相对于传统排序方法,排序网络的优势在于该类算法是数据无关的,通过构造多个比较器可以很简单的实现并行计算。

从定义上了解下什么是双调序列(由非严格增序列X和非严格降序列Y所构成的任意组合多属于双调序列),定义如下:
一个序列 a1,a2, …,an 是双调序列,必须满足以下条件: 
(1)存在一个 ak(1 ≤ k ≤ n),使得 a1 ≥ … ≥ ak ≤ … ≤ an 成立;
(2)序列能够循环移位满足条件(1)

什么是Batcher定理

将任意一个长为2n的双调序列A分为等长的两半X和Y,将X中的元素与Y中的元素一一按原序比较,即a[i]与a[i+n] (i < n)比较,将较大者放入MAX序列,较小者放入MIN序列。则得到的MAX和MIN序列仍然是双调序列,并且MAX序列中的任意一个元素不小于MIN序列中的任意一个元素。


其实,到现在还有两个问题:
  • 怎么把普通序列变成双调序列?

  • 怎么对双调序列进行排序?


02 算法流程
如何进行双调排序(Bitonic sort)?



针对双调序列Z,根据Batcher定理,Z可以划分为2个双调序列X和Y,然后继续对X和Y进行递归划分,得到更短的双调序列,直到得到的子序列长度为1为止。这时的输出序列按单调递增顺序排列。

如图所示,针对序列Z=[10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]进行升序排序:
  • 把序列Z对半分,假设n=2^k=4,然后1和n/2+1比较,小的放上,接下来2和n/2+2比较,小的放上,以此类推;

  • 看成两个(n/2)长度的序列,因为都是双调序列,可以重复上面过程;

  • 总共重复k=4轮,即最后一轮已经是长度是2的序列比较了,就可得到最终的排序结果。

  • 该过程是up bottom的


怎么把普通序列变成双调序列?

看完上面双调排序的过程你可能也猜到了,构造双调序列采用分治(divide and conquer)思路是非常优雅的,这个过程我们叫做Bitonic merge

将两个相邻&单调性相反的单调序列看作一个双调序列, 每次将这两个单调序列merge生成一个新的双调序列, 然后进行双调排序,不断上述过程。流程如下:

对于无序数组 A,相邻的两个数肯定是双调序列,比如 (a0,a1), (a2,a3) 等 

  1. 步长为 2:(a0,a1) 传入bitonic sort,变成升序序列;(a2,a3) 传入 bitonic sort,变成降序序列;

  2. 步长为 4:(a0, a1, a2, a3) 是双调序列,传入 bitonic sort 变成升序序列,(a4, a5, a6, a7) 也是双调的,传入 bitonic sort变成降序序列;

  3. 步长依次为 2^n: 最后变为前 n/2 元素是升序,后 n/2 是降序的完整双调序列。


和前面sort的思路正相反, 是一个bottom up的过程。

03 Python实现

复杂度:

  • 串行方式,复杂度O(nlog(n))

  •  n/2个并行,复杂度O(log(n))


下面这个Demo详细介绍了如何从无序变成双调序列进行升序的过程。
初始数据
 36 15 27 57  4 32 69 46 76 99 21 31 92 31 90 13

# 自底向上的构建过程中也包含了自顶向下的排序过程

步长为: 1, 序列长: 2,  15 36

步长为: 1, 序列长: 2,  57 27

步长为: 1, 序列长: 2,   4 32

步长为: 1, 序列长: 2,  69 46

步长为: 1, 序列长: 2,  76 99

步长为: 1, 序列长: 2,  31 21

步长为: 1, 序列长: 2,  31 92

步长为: 1, 序列长: 2,  90 13

步长为: 2, 序列长: 4,  15 27 57 36

步长为: 1, 序列长: 4,  15 27 36 57

步长为: 2, 序列长: 4,  69 46  4 32

步长为: 1, 序列长: 4,  69 46 32  4

步长为: 2, 序列长: 4,  31 21 76 99

步长为: 1, 序列长: 4,  21 31 76 99

步长为: 2, 序列长: 4,  90  92 31 13

步长为: 1, 序列长: 4,  92 90 31 13

步长为: 4, 序列长: 8,  15 27 32  4 69 46 36 57

步长为: 2, 序列长: 8,  15  4 32 27 36 46 69 57

步长为: 1, 序列长: 8,   4 15 27 32 36 46 57 69

步长为: 4, 序列长: 8,  92 90 76 99 21 31 31 13

步长为: 2, 序列长: 8,  92 99 76 90 31 31 21 13

步长为: 1, 序列长: 8,  99 92  90 76 31 31 21 13

双调序列
  4 15 27 32 36 46 57 69 99 92 90 76 31 31 21 13

# 自顶向下完成双调序列的排序

步长为: 8, 序列长: 16,   4 15 27 32 31 31 21 13 99 92 90 76 36 46 57 69

步长为: 4, 序列长: 16,   4 15 21 13 31 31 27 32 36 46 57 69 99 92 90 76

步长为: 2, 序列长: 16,   4 13 21  15 27 31 31 32 36 46 57 69 90 76 99 92

步长为: 1, 序列长: 16,   4 13 15 21 27 31 31 32 36 46 57 69 76 90 92 99

双调排序
  4 13 15 21 27 31 31 32 36 46 57 69 76 90 92 99


Python实现
"""
Python program for Bitonic Sort.
Note that this program works only when size of input is a power of 2.
"""

from typing import List


def comp_and_swap(array: List[int], index1: int, index2: int, direction: int) -> None:
    """Compare the value at given index1 and index2 of the array and swap them as per
    the given direction.
    The parameter direction indicates the sorting direction, ASCENDING(1) or
    DESCENDING(0); if (a[i] > a[j]) agrees with the direction, then a[i] and a[j] are
    interchanged.
    >>> arr = [12, 42, -21, 1]
    >>> comp_and_swap(arr, 1, 2, 1)
    >>> print(arr)
    [12, -21, 42, 1]
    >>> comp_and_swap(arr, 1, 2, 0)
    >>> print(arr)
    [12, 42, -21, 1]
    >>> comp_and_swap(arr, 0, 3, 1)
    >>> print(arr)
    [1, 42, -21, 12]
    >>> comp_and_swap(arr, 0, 3, 0)
    >>> print(arr)
    [12, 42, -21, 1]
    """

    if (direction == 1 and array[index1] > array[index2]) or (
        direction == 0 and array[index1]     ):
        array[index1], array[index2] = array[index2], array[index1]


def bitonic_merge(array: List[int], low: int, length: int, direction: int) -> None:
    """
    It recursively sorts a bitonic sequence in ascending order, if direction = 1, and in
    descending if direction = 0.
    The sequence to be sorted starts at index position low, the parameter length is the
    number of elements to be sorted.
    >>> arr = [12, 42, -21, 1]
    >>> bitonic_merge(arr, 0, 4, 1)
    >>> print(arr)
    [-21, 1, 12, 42]
    >>> bitonic_merge(arr, 0, 4, 0)
    >>> print(arr)
    [42, 12, 1, -21]
    """

    if length > 1:
        middle = int(length / 2)
        for i in range(low, low + middle):
            comp_and_swap(array, i, i + middle, direction)
        bitonic_merge(array, low, middle, direction)
        bitonic_merge(array, low + middle, middle, direction)


def bitonic_sort(array: List[int], low: int, length: int, direction: int) -> None:
    """
    This function first produces a bitonic sequence by recursively sorting its two
    halves in opposite sorting orders, and then calls bitonic_merge to make them in the
    same order.
    >>> arr = [12, 34, 92, -23, 0, -121, -167, 145]
    >>> bitonic_sort(arr, 0, 8, 1)
    >>> arr
    [-167, -121, -23, 0, 12, 34, 92, 145]
    >>> bitonic_sort(arr, 0, 8, 0)
    >>> arr
    [145, 92, 34, 12, 0, -23, -121, -167]
    """

    if length > 1:
        middle = int(length / 2)
        bitonic_sort(array, low, middle, 1)
        bitonic_sort(array, low + middle, middle, 0)
        bitonic_merge(array, low, length, direction)


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item.strip()) for item in user_input.split(",")]

    bitonic_sort(unsorted, 0, len(unsorted), 1)
    print("\nSorted array in ascending order is: ", end="")
    print(*unsorted, sep=", ")

    bitonic_merge(unsorted, 0, len(unsorted), 0)
    print("Sorted array in descending order is: ", end="")
    print(*unsorted, sep=", ")


Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/113526
 
354 次点击