SortRadix.cc

#include <concepts>
#include <format>
#include <iostream>
#include <random>

#include "vector.hh"

// least significant digit first radix sort
template <class T>
  requires std::integral<T>
void LSD(ns::vector<T> &A) {
  constexpr int BYTES_PER_ELEMENT = sizeof(T);
  constexpr int BITS_PER_BYTE = 8;
  constexpr int RADIX = 1 << BITS_PER_BYTE;
  constexpr int MASK = RADIX - 1;

  int n = A.size();
  ns::vector<T> aux(n);

  for (int d = 0; d < BYTES_PER_ELEMENT; d++) {
    ns::vector<int> count(RADIX + 1, 0);
    for (int i = 0; i < n; i++) {
      int c = (A[i] >> BITS_PER_BYTE * d) & MASK;
      count[c + 1]++;
    }

    for (int r = 0; r < RADIX; r++) count[r + 1] += count[r];

    if constexpr (std::is_signed_v<T>) {
      if (d == BYTES_PER_ELEMENT - 1) {
        int shift1 = count[RADIX] - count[RADIX / 2];
        int shift2 = count[RADIX / 2];
        // shift right positive integer
        for (int r = 0; r < RADIX / 2; r++) count[r] += shift1;
        // shift left negative integer
        for (int r = RADIX / 2; r < RADIX; r++) count[r] -= shift2;
      }
    }

    for (int i = 0; i < n; i++) {
      int c = (A[i] >> BITS_PER_BYTE * d) & MASK;
      aux[count[c]++] = A[i];
    }
    std::swap(A, aux);

    std::cout << '\n';
    std::ranges::for_each(
        A, [](auto x) { std::cout << std::format("{:+}\t", x); });
    std::cout << '\n';
  }
}

int main() {
  std::mt19937 mt(std::random_device{}());
  std::uniform_int_distribution<int> rand(0x80000000, 0x7fffffff);

  ns::vector<int> A(8);
  for (auto &e : A) {
    e = rand(mt);
    std::cout << e << '\t';
  }
  std::cout << '\n';

  LSD(A);
  std::cout << '\n';
  std::ranges::for_each(A,
                        [](auto x) { std::cout << std::format("{:+}\t", x); });
  std::cout << "\n\n";

  std::cout << std::format("{}",
                           std::ranges::is_sorted(A) ? "Sorted" : "Unsorted");
  std::cout << '\n';
}