Can Bitonic Sort handle non-power-of-2 data in a non-recursive implementation ? (without using the method of padding to the power of 2)

user_19637126 0
Viewed 64

Below is a pseudocode for a non-recursive implementation of Bitonic sort.

I can't think of a way to modify the pseudocode to handle data input of any size without using the method of padding the data to the power of 2.

void impBitonicSort() {
    int i, j, k;
    for (k = 2; k <= N; k = 2 * k) {
        for (j = k >> 1; j > 0; j = j >> 1) {
            for (i = 0; i < N; i++) {
                int ij = i ^ j;
                if ((ij) > i) {
                    if ((i & k) == 0 && a[i] > a[ij]) exchange(i, ij);
                    if ((i & k) != 0 && a[i] < a[ij]) exchange(i, ij);
                }
            }
        }
    }
}
sorting algorithm
1 Answers

The zero-one principle for sorting networks implies that we can just skip the comparisons involving missing elements. The code in the question uses backward comparators, so we have to switch to a bitonic sort that uses only forward comparators. In tested C++:

#include <algorithm>
#include <cstdio>
#include <numeric>
#include <vector>

template <typename T>
void comparator(std::vector<T> &a, std::size_t i, std::size_t j) {
  if (i < j && j < a.size() && a[j] < a[i])
    std::swap(a[i], a[j]);
}

template <typename T> void impBitonicSort(std::vector<T> &a) {
  // Iterate k as if the array size were rounded up to the nearest power of two.
  for (std::size_t k = 2; (k >> 1) < a.size(); k <<= 1) {
    for (std::size_t i = 0; i < a.size(); i++)
      comparator(a, i, i ^ (k - 1));
    for (std::size_t j = k >> 1; 0 < j; j >>= 1)
      for (std::size_t i = 0; i < a.size(); i++)
        comparator(a, i, i ^ j);
  }
}

int main() {
  for (int n = 2; n <= 8; n++) {
    std::vector<int> unsorted(n);
    std::iota(unsorted.begin(), unsorted.end(), 0);
    do {
      auto sorted = unsorted;
      impBitonicSort(sorted);
      if (!std::is_sorted(sorted.begin(), sorted.end())) {
        for (int i : unsorted)
          std::printf(" %d", i);
        std::printf("\n");
        return 1;
      }
    } while (std::next_permutation(unsorted.begin(), unsorted.end()));
  }
}
user_21446690
Related