Sắp xếp bitonic là thuật toán sắp xếp song song được tạo để triển khai tốt nhất và có cách sử dụng tối ưu với phần cứng và mảng bộ xử lý song song .
Nó không phải là cách hiệu quả nhất so với sắp xếp hợp nhất. Nhưng nó là tốt cho việc thực hiện song song. Điều này là do trình tự so sánh được xác định trước giúp so sánh độc lập với dữ liệu sẽ được sắp xếp.
Để sắp xếp bitonic hoạt động hiệu quả, số phần tử phải ở một loại số lượng cụ thể, tức là thứ tự 2 ^ n .
Một phần chính của sắp xếp bitonic là chuỗi bitonic là một chuỗi có giá trị các phần tử của nó tăng đầu tiên và sau đó giảm .
Chuỗi biton là một mảng arr [0… (n-1)] nếu có giá trị chỉ số i trong phạm vi từ 0 đến n-1. Giá trị của arr [i] lớn nhất trong mảng. tức là
arr[0] <= arr[1] … <= arr[i] and arr[i] >= arr[i+1] … >= aar[n-1]
Các đặc tính đặc biệt của chuỗi bitonic -
-
Chuỗi bitonic có thể được quay trở lại chuỗi bitonic.
-
Một chuỗi có các phần tử theo thứ tự tăng và giảm là một chuỗi bitonic.
Tạo chuỗi bitonic
Để tạo chuỗi bitonic, chúng tôi sẽ tạo hai chuỗi con, một chuỗi có các phần tử tăng dần và một chuỗi có các phần tử giảm dần.
Ví dụ:hãy xem trình tự arr [] và chuyển đổi trình tự sau thành trình tự bitonic.
arr[] = {3, 4, 1, 9, 2, 7, 5, 6} Đầu tiên, chúng tôi sẽ tạo các cặp phần tử và sau đó tạo một chuỗi bitonic của các phần tử này theo cách một phần tử theo thứ tự tăng dần và phần tử kia theo thứ tự giảm dần.
Đối với mảng của chúng tôi, hãy tạo các cặp theo chuỗi bitonic.
arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)}
// creating bitonic sequence pairs…
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)} Sau đó, chúng ta sẽ tạo ra các cặp của các cặp này. tức là 4 phần tử theo dãy bitonic và so sánh các phần tử với là 2 khoảng cách [tức là tôi với i + 2].
arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)} Bitonic tăng dần trong tập hợp đầu tiên sẽ được tạo dưới dạng -
(3, 4, 9, 1) : comparing two distant elements. (3, 1, 9, 4) : Now, check adjacent elements. (1, 3, 4, 9) -> ascending bitonic sequence.
Bitonic giảm dần trong tập thứ hai sẽ được tạo dưới dạng -
(2, 7, 6, 5) : comparing two distant elements. (6, 7, 2, 5) : Now, check adjacent elements. (7, 6, 5, 2) -> descending bitonic sequence.
Cuối cùng, chúng ta sẽ nhận được chuỗi bitonic có kích thước 8.
1, 3, 4, 9, 7, 6, 5, 2
Bây giờ, vì chúng ta đã học về chuỗi bitonic. Chúng tôi sẽ biết về Phân loại Bitonic .
SẮP XẾP BITONIC
Để sắp xếp một chuỗi bitonic bằng cách sử dụng sắp xếp bitonic bằng các bước sau -
Bước 1 - Tạo chuỗi bitonic.
Bước 2 - Bây giờ, chúng ta có một chuỗi bitonic với một phần theo thứ tự tăng dần và phần khác theo thứ tự giảm dần.
Bước 3 - Chúng tôi sẽ so sánh và hoán đổi các phần tử đầu tiên của cả hai nửa. Sau đó, các phần tử thứ hai, thứ ba, thứ tư cho chúng.
Bước 4 - Chúng tôi sẽ so sánh và hoán đổi từng phần tử thứ hai của chuỗi.
Bước 5 - Cuối cùng, chúng tôi sẽ so sánh và hoán đổi các phần tử liền kề của dãy.
Bước 6 - Sau tất cả các lần hoán đổi, chúng ta sẽ nhận được mảng đã sắp xếp.
Ví dụ
Chương trình cho thấy việc 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