Bitonic Sort ใน C++

Bitonic Sort เป็นอัลกอริทึมการจัดเรียงแบบขนาน (parallel sorting algorithm) ที่สร้างขึ้นสำหรับการนำไปใช้งานที่ดีที่สุด และมีการใช้งานเหมาะสมที่สุดกับฮาร์ดแวร์และ parallel processor array

มันไม่ใช่วิธีที่มีประสิทธิภาพที่สุดเมื่อเทียบกับ Merge Sort แต่มันดีสำหรับการนำไปใช้แบบขนาน เนื่องจากลำดับการเปรียบเทียบ (comparison sequence) ที่กำหนดไว้ล่วงหน้า ทำให้การเปรียบเทียบเป็นอิสระจากข้อมูลที่จะจัดเรียง

เพื่อให้ Bitonic Sort ทำงานได้อย่างมีประสิทธิภาพ จำนวนองค์ประกอบควรเป็นประเภทปริมาณเฉพาะ คือ อันดับ 2^n

ส่วนสำคัญของ Bitonic Sort คือ Bitonic Sequence ซึ่งคือลำดับที่ค่าขององค์ประกอบ เพิ่มขึ้นก่อน แล้ว ลดลง

Bitonic Sequence คืออาร์เรย์ arr[0 ... (n-1)] หากมีค่าดัชนี i ภายในช่วง 0 ถึง n-1 ที่ค่าของ arr[i] เป็นค่าสูงสุดในอาร์เรย์ คือ

arr[0] ≤ arr[1] ... ≤ arr[i] และ arr[i] ≥ arr[i+1] ... ≥ arr[n-1]

ลักษณะพิเศษของ Bitonic Sequence −

• Bitonic Sequence สามารถหมุนกลับเป็น Bitonic Sequence ได้
• ลำดับที่มีองค์ประกอบเรียงเพิ่มและลดเป็น Bitonic Sequence

การสร้าง Bitonic Sequence

เพื่อสร้าง Bitonic Sequence เราจะสร้าง 2 sub-sequences หนึ่งเรียงเพิ่ม และอีกหนึ่งเรียงลด

เช่น มาดูลำดับ arr[] และแปลงลำดับต่อไปนี้เป็น Bitonic Sequence

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

ก่อนอื่น เราจะจับคู่องค์ประกอบ แล้วสร้าง Bitonic Sequence ของคู่เหล่านี้ โดยให้หนึ่งคู่เรียงเพิ่ม และอีกคู่เรียงลด สลับกันไป

สำหรับอาร์เรย์ของเรา มาสร้างคู่ใน Bitonic Sequence

arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)} // สร้างคู่ Bitonic Sequence...
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)}

จากนั้น เราจะสร้างคู่ของคู่เหล่านี้ คือ Bitonic Sequence ขนาด 4 และเปรียบเทียบองค์ประกอบที่ห่างกัน 2 ตำแหน่ง [เช่น i กับ i+2]

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

Bitonic เรียงเพิ่มในชุดแรกจะสร้างได้เป็น −

(3, 4, 9, 1) : เปรียบเทียบองค์ประกอบที่ห่าง 2 ตำแหน่ง
(3, 1, 9, 4) : ตอนนี้ ตรวจสอบองค์ประกอบที่อยู่ติดกัน
(1, 3, 4, 9) -> ascending bitonic sequence

Bitonic เรียงลดในชุดที่สองจะสร้างได้เป็น −

(2, 7, 6, 5) : เปรียบเทียบองค์ประกอบที่ห่าง 2 ตำแหน่ง
(6, 7, 2, 5) : ตอนนี้ ตรวจสอบองค์ประกอบที่อยู่ติดกัน
(7, 6, 5, 2) -> descending bitonic sequence

ในที่สุด เราจะได้ Bitonic Sequence ขนาด 8

1, 3, 4, 9, 7, 6, 5, 2

ตอนนี้ เราได้เรียนรู้เกี่ยวกับ Bitonic Sequence แล้ว เราจะรู้เกี่ยวกับ Bitonic Sorting

BITONIC SORTING

เพื่อจัดเรียง Bitonic Sequence โดยใช้ Bitonic Sorting ด้วยขั้นตอนเหล่านี้ −

ขั้นตอน 1 − สร้าง Bitonic Sequence

ขั้นตอน 2 − ตอนนี้เรามี Bitonic Sequence ที่ส่วนหนึ่งเรียงเพิ่ม และอีกส่วนเรียงลด

ขั้นตอน 3 − เราจะเปรียบเทียบและสลับองค์ประกอบแรกของทั้งสองครึ่ง แล้วองค์ประกอบที่สอง สาม สี่ ของพวกมัน

ขั้นตอน 4 − เราจะเปรียบเทียบและสลับ ทุกๆ องค์ประกอบที่สองของลำดับ

ขั้นตอน 5 − ท้ายสุด เราจะเปรียบเทียบและสลับองค์ประกอบที่อยู่ติดกันของลำดับ

ขั้นตอน 6 − หลังจากสลับเสร็จทั้งหมด เราจะได้อาร์เรย์ที่จัดเรียงแล้ว

ตัวอย่างโปรแกรม

#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;
}

เอาต์พุต

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