Sắp xếp Bitonic trong C++

Sắp xếp Bitonic (Bitonic Sort) là thuật toán sắp xếp song song, thiết kế cho triển khai phần cứng và mảng xử lý song song tối ưu.

Mặc dù không hiệu quả bằng Merge Sort về mặt lý thuyết, nhưng phù hợp cho triển khai song song nhờ trình tự so sánh được định trước, độc lập với dữ liệu.

Để Bitonic Sort hoạt động tốt, số phần tử phải là lũy thừa của 2 (2ⁿ).

Phần quan trọng của Bitonic Sort là dãy Bitonic – dãy mà giá trị trước tăng dần, sau giảm dần.

Dãy Bitonic là mảng arr[0...n-1] nếu tồn tại chỉ số i trong [0, n-1] mà arr[i] là lớn nhất:

arr[0] ≤ arr[1] ... ≤ arr[i] và arr[i] ≥ arr[i+1] ... ≥ arr[n-1]

Đặc điểm đặc biệt của dãy Bitonic

• Dãy Bitonic xoay vòng vẫn là dãy Bitonic.
• Dãy tăng dần hoặc giảm dần thuần túy cũng là dãy Bitonic.

Tạo dãy Bitonic

Tạo hai dãy con: một tăng, một giảm. Ví dụ với mảng:

arr[] = {3, 4, 1, 9, 2, 7, 5, 6}

Tạo cặp bitonic: (3,4), (1,9), (2,7), (5,6) → (3,4), (9,1), (2,7), (6,5)

Gộp cặp thành nhóm 4: (3,4,9,1), (2,7,6,5)

So sánh phần tử cách 2 vị trí, sau đó so sánh kề nhau để tạo bitonic tăng/giảm.

Kết quả dãy Bitonic kích thước 8: 1, 3, 4, 9, 7, 6, 5, 2

SẮP XẾP BITONIC

Các bước sắp xếp dãy Bitonic:

1. Tạo dãy Bitonic.
2. So sánh và hoán đổi phần tử đầu của hai nửa. Rồi phần tử thứ 2, 3, 4...
3. So sánh và hoán đổi mỗi phần tử cách nhau 2 vị trí.
4. So sánh và hoán đổi các phần tử kề nhau.
5. Sau tất cả hoán đổi, mảng đã sắp xếp.

Ví dụ

Chương trình triển khai Bitonic Sort:

#include<iostream>
using namespace std;

void bitonicSeqMerge(int a[], int start, int BseqSize, int direction) {
    if (BseqSize > 1) {
        int k = BseqSize / 2;
        for (int i = start; i < start + k; i++)
            if (direction == (a[i] > a[i + k]))
                swap(a[i], a[i + k]);
        bitonicSeqMerge(a, start, k, direction);
        bitonicSeqMerge(a, start + k, k, direction);
    }
}

void bitonicSortRec(int a[], int start, int BseqSize, int direction) {
    if (BseqSize > 1) {
        int k = BseqSize / 2;
        bitonicSortRec(a, start, k, 1);
        bitonicSortRec(a, start + k, k, 0);
        bitonicSeqMerge(a, start, BseqSize, direction);
    }
}

void bitonicSort(int a[], int size, int up) {
    bitonicSortRec(a, 0, size, up);
}

int main() {
    int a[] = {5, 10, 51, 8, 1, 9, 6, 22};
    int size = sizeof(a) / sizeof(a[0]);
    printf("Original array: \n");
    for (int i = 0; i < size; i++)
        printf("%d\t", a[i]);
    bitonicSort(a, size, 1);
    printf("\nSorted array: \n");
    for (int i = 0; i < size; i++)
        printf("%d\t", a[i]);
    return 0;
}

Đầu ra

Original array: 5 10 51 8 1 9 6 22
Sorted array: 1 5 6 8 9 10 22 51