What is Bitonic Sort
Bitonic sort is a sorting algorithm that works by repeatedly comparing and swapping pairs of elements in a sequence until the sequence is sorted in ascending or descending order.
Imagine you have a deck of cards that are not in any particular order. Bitonic sort would start by dividing the deck into two equal halves and comparing the cards in each half, swapping any pairs that are out of order. It would then divide each half into two halves and repeat the process, continuing to divide and compare until the entire deck is sorted.
The name "bitonic" comes from the fact that the algorithm works by first sorting the sequence into a "bitonic" sequence, meaning that the elements are first sorted in ascending order and then in descending order. The algorithm then merges these two sequences to produce the final sorted sequence.
Who invented it?
The Bitonic sort algorithm was originally proposed by Ken Batcher in 1968 as a parallel sorting algorithm that could efficiently be implemented on parallel computer architectures. Batcher was a computer scientist and mathematician who made significant contributions to the development of parallel computing and sorting algorithms.
Pseudocode
bitonicSort(arr, low, count, dir)
if count > 1
k = count / 2
bitonicSort(arr, low, k, ascending)
bitonicSort(arr, low + k, k, descending)
bitonicMerge(arr, low, count, dir)
bitonicMerge(arr, low, count, dir)
if count > 1
k = greatestPowerOfTwoLessThan(count)
for i = low to low + count - k - 1
if dir == (arr[i] > arr[i + k])
swap(arr[i], arr[i + k])
bitonicMerge(arr, low, k, dir)
bitonicMerge(arr, low + k, count - k, dir)
greatestPowerOfTwoLessThan(n)
k = 1
while k < n
k = k << 1
return k >> 1
In this pseudocode, arr is the array to be sorted, low is the starting index of the subarray to be sorted, count is the number of elements in the subarray to be sorted, and dir specifies the sorting direction (ascending or descending). The bitonicSort function first recursively calls itself to sort the two halves of the subarray, and then calls the bitonicMerge function to merge the two sorted halves.
The bitonicMerge function first finds the largest power of two that is less than count, and then iterates over the subarray, swapping elements if they are out of order according to the sorting direction. It then recursively calls itself to merge the two subarrays resulting from the split, one sorted in ascending order and the other in descending order.
Finally, the greatestPowerOfTwoLessThan function finds the largest power of two that is less than the input n.
The bitonicMerge function first finds the largest power of two that is less than count, and then iterates over the subarray, swapping elements if they are out of order according to the sorting direction. It then recursively calls itself to merge the two subarrays resulting from the split, one sorted in ascending order and the other in descending order.
Finally, the greatestPowerOfTwoLessThan function finds the largest power of two that is less than the input n.
Sample Code
// C++ code snippet
void bitonicSort(int arr[], int low, int count, bool dir) {
if (count > 1) {
int k = count / 2;
bitonicSort(arr, low, k, true);
bitonicSort(arr, low + k, k, false);
bitonicMerge(arr, low, count, dir);
}
}
void bitonicMerge(int arr[], int low, int count, bool dir) {
if (count > 1) {
int k = greatestPowerOfTwoLessThan(count);
for (int i = low; i < low + count - k; i++) {
if (dir == (arr[i] > arr[i + k])) {
swap(arr[i], arr[i + k]);
}
}
bitonicMerge(arr, low, k, dir);
bitonicMerge(arr, low + k, count - k, dir);
}
}
int greatestPowerOfTwoLessThan(int n) {
int k = 1;
while (k < n) {
k = k << 1;
}
return k >> 1;
}
int main() {
int arr[] = { 3, 7, 4, 8, 6, 2, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
bool dir = true; // true for ascending, false for descending
bitonicSort(arr, 0, n, dir);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
# Python code snippet
def bitonicSort(arr, low, count, dir):
if count > 1:
k = count // 2
bitonicSort(arr, low, k, True)
bitonicSort(arr, low + k, k, False)
bitonicMerge(arr, low, count, dir)
def bitonicMerge(arr, low, count, dir):
if count > 1:
k = greatestPowerOfTwoLessThan(count)
for i in range(low, low + count - k):
if dir == (arr[i] > arr[i + k]):
arr[i], arr[i + k] = arr[i + k], arr[i]
bitonicMerge(arr, low, k, dir)
bitonicMerge(arr, low + k, count - k, dir)
def greatestPowerOfTwoLessThan(n):
k = 1
while k < n:
k = k << 1
return k >> 1
arr = [3, 7, 4, 8, 6, 2, 1, 5]
n = len(arr)
dir = True # True for ascending, False for descending
bitonicSort(arr, 0, n, dir)
print("Sorted array:", arr)
public class BitonicSort {
public static void main(String[] args) {
int[] arr = {3, 7, 4, 8, 6, 2, 1, 5};
int n = arr.length;
boolean dir = true; // true for ascending, false for descending
bitonicSort(arr, 0, n, dir);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
public static void bitonicSort(int[] arr, int low, int count, boolean dir) {
if (count > 1) {
int k = count / 2;
bitonicSort(arr, low, k, true);
bitonicSort(arr, low + k, k, false);
bitonicMerge(arr, low, count, dir);
}
}
public static void bitonicMerge(int[] arr, int low, int count, boolean dir) {
if (count > 1) {
int k = greatestPowerOfTwoLessThan(count);
for (int i = low; i < low + count - k; i++) {
if (dir == (arr[i] > arr[i + k])) {
int temp = arr[i];
arr[i] = arr[i + k];
arr[i + k] = temp;
}
}
bitonicMerge(arr, low, k, dir);
bitonicMerge(arr, low + k, count - k, dir);
}
}
public static int greatestPowerOfTwoLessThan(int n) {
int k = 1;
while (k < n) {
k = k << 1;
}
return k >> 1;
}
}