雙調排序

雙調排序是一種並行排序演算法執行O(N 2 log n)的比較。 雖然比較的數量多於任何其他流行的排序演算法，但它對並行實現的效果更好，因為元素以預定義的順序進行比較，而這些序列不能依賴於被排序的數據。預定義的序列稱為雙調(Bitonic)序列。

1. 什麼是雙調(Bitonic)序列？

要理解雙調排序，需要首先來瞭解雙調序列。 雙調序列是其中元素首先按遞增順序然後在某個特定索引之後開始遞減的序列。 如果存在索引i，則數組A [0 ... i ... n-1]稱為雙調，

A[0] < A[1] < A[2] .... A[i-1] < A[i] > A[i+1] > A[i+2] > A[i+3] > ... >A[n-1]

其中，0 <= i <= n-1。雙調排序的旋轉也是雙調。

如何將隨機序列轉換為雙調序列？

考慮n個元素的序列A[0 ... n-1]。 首先通過使用序列的4個元素開始構建雙調序列。 按昇冪對前2個元素進行排序，按降序對最後2個元素進行排序，將該對連接起來形成4個元素的雙調序列。 對剩餘的元素對重複此過程，直到找到雙調序列。

在此步驟之後，得到給定序列的雙調序列為：2,10,20,30,5,5,4,3。

2. 雙調排序

雙調排序主要涉及以下幾個基本步驟。

• 在上述步驟中形成的給定隨機序列形成一個雙調序列。 可以將其視為程式的第一步。 在這一步之後，得到一個序列，其前半部分按昇冪排序，而第二步按降序排序。
• 將前半部分的第一個元素與後半部分的第一個元素進行比較，然後將前半部分的第二個元素與後半部分的第二個元素進行比較，依此類推。 如果發現後半部分中的任何元素較小，則交換元素。
• 在上面的步驟之後，得到的前半部分中的所有元素都小於下半部分中的所有元素。 比較和交換產生每個n/2長度的兩個序列。 在第二步中遞歸地重複執行到每個序列的過程，直到得到長度為n的單個排序序列。

複雜性

使用C語言實現雙調排序的代碼如下 -

//this program works when size of input is power of 2.
#include<stdio.h>
void exchange(int arr[], int i, int j, int d)
{
    int temp;
    if (d==(arr[i]>arr[j]))
    {
            temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
void merge(int arr[], int l, int c, int d)
{
    int k,i;
    if (c>1)
    {
        k = c/2;
        for (i=l; i<l+k; i++)
            exchange(arr, i, i+k, d);
        merge(arr, l, k, d);
        merge(arr, l+k, k, d);
    }
}
void bitonicSort(int arr[],int l, int c, int d)
{
    int k;
    if (c>1)
    {
        k = c/2;
        bitonicSort(arr, l, k, 1);
        bitonicSort(arr, l+k, k, 0);
        merge(arr,l, c, d);
    }
}

void sort(int arr[], int n, int order)
{
    bitonicSort(arr,0, n, order);
}
int main()
{
    int arr[]= {1, 10, 2, 3, 1, 23, 45, 21};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;
    int order = 1;
    sort(arr, n, order);

    printf("Sorted array: \n");
    for (i=0; i<n; i++)
        printf("%d ", arr[i]);
}

執行上面示例代碼，得到以下結果：

Sorted array:
1 1 2 3 10 21 23 45

使用Java語言實現雙調排序的代碼如下 -

//this program works when size of input is power of 2.
public class BitonicSort
{
    static void exchange(int arr[], int i, int j, boolean d)
    {
        int temp;
        if (d==(arr[i]>arr[j]))
        {
                temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    static void merge(int arr[], int l, int c, boolean d)
    {
        int k,i;
        if (c>1)
        {
            k = c/2;
            for (i=l; i<l+k; i++)
                exchange(arr, i, i+k, d);
            merge(arr, l, k, d);
            merge(arr, l+k, k, d);
        }
    }
    static void bitonicSort(int arr[],int l, int c, boolean d)
    {
        int k;
        if (c>1)
        {
            k = c/2;
            bitonicSort(arr, l, k, true);
            bitonicSort(arr, l+k, k, false);
            merge(arr,l, c, d);
        }
    }

    static void sort(int arr[], int n, boolean order)
    {
        bitonicSort(arr,0, n, order);
    }
    public static void main(String[] args)
    {
        int arr[]= {1, 10, 2, 3, 1, 23, 45, 21};
        int n = arr.length;
        int i;
        boolean order = true;
        sort(arr, n, order);

        System.out.println("Sorted array: \n");
        for (i=0; i<n; i++)
            System.out.println(arr[i]);
    }
}

執行上面示例代碼，得到以下結果：

Sorted array:

1    1    2    3    10    21    23    45

使用C#語言實現雙調排序的代碼如下 -

//this program works when size of input is power of 2.
using System;
public class BitonicSort
{
    static void exchange(int[] arr, int i, int j, bool d)
    {
        int temp;
        if (d==(arr[i]>arr[j]))
        {
                temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    static void merge(int[] arr, int l, int c, bool d)
    {
        int k,i;
        if (c>1)
        {
            k = c/2;
            for (i=l; i<l+k; i++)
                exchange(arr, i, i+k, d);
            merge(arr, l, k, d);
            merge(arr, l+k, k, d);
        }
    }
    static void bitonicSort(int[] arr,int l, int c, bool d)
    {
        int k;
        if (c>1)
        {
            k = c/2;
            bitonicSort(arr, l, k, true);
            bitonicSort(arr, l+k, k, false);
            merge(arr,l, c, d);
        }
    }

    static void sort(int[] arr, int n, bool order)
    {
        bitonicSort(arr,0, n, order);
    }
    public void Main()
    {
        int[] arr= {1, 10, 2, 3, 1, 23, 45, 21};
        int n = arr.Length;
        int i;
        bool order = true;
        sort(arr, n, order);

        Console.WriteLine("Sorted array: \n");
        for (i=0; i<n; i++)
            Console.WriteLine(arr[i]+"  ");
    }
}