updated PR with printing the circuit code
fixes #50
Bitonic Sort is a parallel sorting algorithm notable for its ability to efficiently sort sequences of elements using a divide-and-conquer approach. Originally designed for implementation in parallel computing architectures, Bitonic Sort operates by recursively sorting subsequences in a bitonic manner, ultimately resulting in a sorted sequence.
The key characteristic of Bitonic Sort is its property of being able to sort sequences of length that are a power of two in 𝑂
(
log
2
𝑛
)
O(log
2
n) time complexity. This efficiency makes it particularly suitable for parallel processing environments where tasks can be distributed across multiple processors.
The algorithm works as follows:
Bitonic Sequence Creation: Initially, the input sequence is partitioned into two subsequences of equal length, each forming a bitonic sequence. A bitonic sequence is defined as a sequence that first monotonically increases and then monotonically decreases. Bitonic Sorting: Each bitonic sequence is recursively sorted. This involves dividing the sequence into two halves and recursively sorting each half into a bitonic sequence. Bitonic Merge: Once all subsequences are sorted, pairs of bitonic sequences are merged together in a bitonic manner. This involves comparing and swapping elements to form a bitonic sequence. Final Merge: Finally, the remaining bitonic sequences are merged together to form a single sorted sequence. In HierarQcal, Bitonic Sort can be implemented using quantum circuit operations to perform comparisons and swaps. The recursive nature of Bitonic Sort can be represented as a hierarchical structure of quantum circuits, where each level corresponds to a level of recursion in the algorithm. The parallel nature of quantum computing can potentially offer advantages for sorting large datasets by executing sorting operations in parallel.
updated PR with printing the circuit code fixes #50 Bitonic Sort is a parallel sorting algorithm notable for its ability to efficiently sort sequences of elements using a divide-and-conquer approach. Originally designed for implementation in parallel computing architectures, Bitonic Sort operates by recursively sorting subsequences in a bitonic manner, ultimately resulting in a sorted sequence.
The key characteristic of Bitonic Sort is its property of being able to sort sequences of length that are a power of two in 𝑂 ( log 2 𝑛 ) O(log 2 n) time complexity. This efficiency makes it particularly suitable for parallel processing environments where tasks can be distributed across multiple processors.
The algorithm works as follows:
Bitonic Sequence Creation: Initially, the input sequence is partitioned into two subsequences of equal length, each forming a bitonic sequence. A bitonic sequence is defined as a sequence that first monotonically increases and then monotonically decreases. Bitonic Sorting: Each bitonic sequence is recursively sorted. This involves dividing the sequence into two halves and recursively sorting each half into a bitonic sequence. Bitonic Merge: Once all subsequences are sorted, pairs of bitonic sequences are merged together in a bitonic manner. This involves comparing and swapping elements to form a bitonic sequence. Final Merge: Finally, the remaining bitonic sequences are merged together to form a single sorted sequence. In HierarQcal, Bitonic Sort can be implemented using quantum circuit operations to perform comparisons and swaps. The recursive nature of Bitonic Sort can be represented as a hierarchical structure of quantum circuits, where each level corresponds to a level of recursion in the algorithm. The parallel nature of quantum computing can potentially offer advantages for sorting large datasets by executing sorting operations in parallel.