Small array sort test

sort.cpp

#include <stdlib.h>
#include <assert.h>
#include <intrin.h>
#include <array>

#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
#undef min
#undef max


using array_t = std::array<float, 64>;

// generate a random float
float randf() {
  return float(rand() & 0xffff) / float(0x1000);
}

// fill the array with random numbers
void array_fill(array_t &array) {
  for (float &f : array) {
    f = randf();
  }
}

// check the array is completely sorted
void array_test(const array_t &array) {
  for (size_t s = 1; s < array.size(); ++s) {
    assert(array[s - 1] <= array[s]);
  }
}

// swappy insertion sort
// 1882
void array_sort_1(array_t &array) {
  for (size_t i = 0; i < array.size(); ++i) {
    for (size_t j = array.size()-1; j > i; --j) {
      if (array[j] < array[i]) {
        std::swap(array[j], array[i]);
      }
    }
  }
}

// swappy insertion sort with reverse swap
// 2393
void array_sort_2(array_t &array) {
  for (size_t i = 0; i < array.size(); ++i) {
    for (size_t j = i + 1; j < array.size(); ++j) {
      if (array[j] < array[i]) {
        std::swap(array[j], array[i]);
      }
    }
  }
}

// insertion sort
// 1494
void array_sort_3(array_t &array) {
  for (uint32_t i = 1; i < array.size(); ++i) {
    for (uint32_t j = i; j > 0; --j) {
      auto &x = array[j-1];
      auto &y = array[j];
      if (x < y)
        break;
      std::swap(x, y);
    }
  }
}

// comb sort
// 1184
void array_sort_4(array_t &array) {
  // first comb pass
  bool busy = true;
  uint32_t gap = (array.size() * 2) / 3;
  while (busy) {
    busy = (gap > 1);
    for (size_t i = gap; i < array.size(); ++i) {
      auto &x = array[i - gap];
      auto &y = array[i];
      if (x > y) {
        std::swap(x, y);
      }
    }
    gap = (gap * 100) / 130;
  }
}

// heap sort, heapify
void array_sort_5_pre(array_t &array) {
  for (int i = 1; i < array.size(); ++i) {
    for (int j = i / 2, k = i;; k = j, j /= 2) {
      auto &x = array[j];
      auto &y = array[k];
      if (y <= x)
        break;
      std::swap(x, y);
      if (j == 1)
        break;
    }
  }
}

// heap sort
// XXX: not tested
void array_sort_5(array_t &array) {
  array_sort_5_pre(array);
  for (int i = array.size() - 1; i > 0; --i) {
    // swap max with end
    std::swap(array[0], array[i]);
    // bubble down
    for (int j = 0; j < i/2;) {
      auto &x = array[j * 2];
      auto &y = array[j * 2 + 1];
      auto &z = array[j];
      // child 1
      if (x > y) {
        if (x <= z) {
          break;
        }
        std::swap(x, z);
        j = j * 2;
      }
      // child 2
      else {
        if (y <= z) {
          break;
        }
        std::swap(y, z);
        j = j * 2 + 1;
      }
    }
  }
}

// binary insertion sort
// 1495
void array_sort_6(array_t &t) {
  // one by one over all elements
  for (int32_t i = 1; i < t.size(); ++i) {
    // grab new element
    const float v = t[i];
    if (t[i - 1] < v) {
      // early exit when its ordered
      continue;
    }
    // binary insert
    for (int32_t l = 0, r = i - 1, m = 0;;) {
      if (r - l <= 1) {
        m = t[l] > v ? l : r;
        const auto temp = t[i];
        memmove((t.data() + m + 1), t.data() + m, (i - m) * sizeof(float));
        t[m] = temp;
        break;
      }
      m = (l + r) / 2;
      if (t[m] > v) {
        r = m;
      } else {
        l = m;
      }
    }
  }
}

// TODO: Try sorting networks
// 2480
void bubble(array_t &a) {
  for (int32_t i = 1; i < a.size(); ++i) {
    bool swapped = false;
    for (int32_t j = a.size() - 1; j >= i; --j) {
      const float v = a[j];
      if (v < a[j - 1]) {
        std::swap(a[j], a[j - 1]);
        swapped = true;
      }
    }
    if (!swapped)
      break;
  }
}

// bubble sort
// 2442
void array_sort_7(array_t &data) {
  for (int i = 0; i < data.size(); i++) {
    for (int j = 1; j < data.size() - i; j++) {
      if (data[j] > data[j - 1]) {
        std::swap(data[j], data[j - 1]);
      }
    }
  }
}

// comb sort
// 1255
void array_sort_8(array_t &a) {
  uint32_t gap = a.size();
  do {
    gap = (gap * 7) / 8;
    for (uint32_t x = gap, y = 0; x < a.size(); ++x, ++y) {
      if (a[x] < a[y]) {
        std::swap(a[x], a[y]);
      }
    }
  } while (gap > 1);
}

// entry point
int main() {

  // pin to one core
  HANDLE proc = GetCurrentProcess();
  BOOL ret = SetProcessAffinityMask(proc, 0x1);

  array_t array;
  std::array<uint64_t, 128> delta;

  // testing loop
  for (uint64_t &d : delta) {
    uint64_t t1 = __rdtsc();
    for (int j = 0; j < 1000; ++j) {
      array_fill(array);
      array_sort_3(array);
      array_test(array);
    }
    d = __rdtsc() - t1;
  }

  // extract results
  uint64_t delta_min = delta[0];
  uint64_t delta_mean = 0;
  for (uint64_t &d : delta) {
    delta_min = std::min(delta_min, d);
    delta_mean += d;
  }
  delta_mean /= delta.size();

  // print results
  printf("min:  %llu\n", delta_min  / 10000llu);
  printf("mean: %llu\n", delta_mean / 10000llu);
  getchar();

  return 0;
}