| 1 |
// Copyright(C) 1999-2021, 2023, 2024 National Technology & Engineering Solutions |
| 2 |
// of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with |
| 3 |
// NTESS, the U.S. Government retains certain rights in this software. |
| 4 |
// |
| 5 |
// See packages/seacas/LICENSE for details |
| 6 |
/*! |
| 7 |
* The following 'indexed qsort' routine is modified from Sedgewicks |
| 8 |
* algorithm It selects the pivot based on the median of the left, |
| 9 |
* right, and center values to try to avoid degenerate cases occurring |
| 10 |
* when a single value is chosen. It performs a quicksort on |
| 11 |
* intervals down to the EX_QSORT_CUTOFF size and then performs a final |
| 12 |
* insertion sort on the almost sorted final array. Based on data in |
| 13 |
* Sedgewick, the EX_QSORT_CUTOFF value should be between 5 and 20. |
| 14 |
* |
| 15 |
* See Sedgewick for further details |
| 16 |
* Define DEBUG_QSORT at the top of this file and recompile to compile |
| 17 |
* in code that verifies that the array is sorted. |
| 18 |
*/ |
| 19 |
|
| 20 |
#include <EJ_CodeTypes.h> |
| 21 |
#include <cstdint> |
| 22 |
#include <numeric> |
| 23 |
#include <unistd.h> |
| 24 |
|
| 25 |
#include "EJ_index_sort.h" |
| 26 |
|
| 27 |
#define EX_QSORT_CUTOFF 12 |
| 28 |
|
| 29 |
namespace { |
| 30 |
/* swap - interchange v[i] and v[j] */ |
| 31 |
template <typename T, typename INT> void ex_swap(T *v, INT i, INT j) |
| 32 |
{ |
| 33 |
T temp = v[i]; |
| 34 |
v[i] = v[j]; |
| 35 |
v[j] = temp; |
| 36 |
} |
| 37 |
|
| 38 |
template <typename T, typename INT> INT ex_int_median3(T *v, INT iv[], size_t left, size_t right) |
| 39 |
{ |
| 40 |
size_t center = (left + right) / 2; |
| 41 |
|
| 42 |
if (v[iv[left]] > v[iv[center]]) { |
| 43 |
ex_swap(iv, left, center); |
| 44 |
} |
| 45 |
if (v[iv[left]] > v[iv[right]]) { |
| 46 |
ex_swap(iv, left, right); |
| 47 |
} |
| 48 |
if (v[iv[center]] > v[iv[right]]) { |
| 49 |
ex_swap(iv, center, right); |
| 50 |
} |
| 51 |
|
| 52 |
ex_swap(iv, center, right - 1); |
| 53 |
return iv[right - 1]; |
| 54 |
} |
| 55 |
|
| 56 |
template <typename T, typename INT> void ex_int_iqsort(T *v, INT iv[], size_t left, size_t right) |
| 57 |
{ |
| 58 |
if (left + EX_QSORT_CUTOFF <= right) { |
| 59 |
INT pivot = ex_int_median3(v, iv, left, right); |
| 60 |
size_t i = left; |
| 61 |
size_t j = right - 1; |
| 62 |
|
| 63 |
for (;;) { |
| 64 |
while (v[iv[++i]] < v[pivot]) { |
| 65 |
; |
| 66 |
} |
| 67 |
while (v[iv[--j]] > v[pivot]) { |
| 68 |
; |
| 69 |
} |
| 70 |
if (i < j) { |
| 71 |
ex_swap(iv, i, j); |
| 72 |
} |
| 73 |
else { |
| 74 |
break; |
| 75 |
} |
| 76 |
} |
| 77 |
|
| 78 |
ex_swap(iv, i, right - 1); |
| 79 |
ex_int_iqsort(v, iv, left, i - 1); |
| 80 |
ex_int_iqsort(v, iv, i + 1, right); |
| 81 |
} |
| 82 |
} |
| 83 |
|
| 84 |
template <typename T, typename INT> void ex_int_iisort(T *v, INT iv[], size_t N) |
| 85 |
{ |
| 86 |
if (N == 0) { |
| 87 |
return; |
| 88 |
} |
| 89 |
|
| 90 |
size_t ndx = 0; |
| 91 |
|
| 92 |
using TT = typename std::remove_cv_t<T>; |
| 93 |
TT small = v[iv[0]]; |
| 94 |
for (size_t i = 1; i < N; i++) { |
| 95 |
if (v[iv[i]] < small) { |
| 96 |
small = v[iv[i]]; |
| 97 |
ndx = i; |
| 98 |
} |
| 99 |
} |
| 100 |
/* Put smallest value in slot 0 */ |
| 101 |
ex_swap(iv, static_cast<size_t>(0), ndx); |
| 102 |
|
| 103 |
size_t j; |
| 104 |
for (size_t i = 1; i < N; i++) { |
| 105 |
INT tmp = iv[i]; |
| 106 |
for (j = i; v[tmp] < v[iv[j - 1]]; j--) { |
| 107 |
iv[j] = iv[j - 1]; |
| 108 |
} |
| 109 |
iv[j] = tmp; |
| 110 |
} |
| 111 |
} |
| 112 |
|
| 113 |
template <typename T, typename INT> void exi_iqsort(T *v, INT iv[], size_t N) |
| 114 |
{ |
| 115 |
if (N <= 1) { |
| 116 |
return; |
| 117 |
} |
| 118 |
|
| 119 |
ex_int_iqsort(v, iv, 0, N - 1); |
| 120 |
ex_int_iisort(v, iv, N); |
| 121 |
|
| 122 |
#if defined(DEBUG_QSORT) |
| 123 |
fprintf(stderr, "Checking sort of %lu values\n", N + 1); |
| 124 |
int i; |
| 125 |
for (i = 1; i < N; i++) { |
| 126 |
assert(v[iv[i - 1]] <= v[iv[i]]); |
| 127 |
} |
| 128 |
#endif |
| 129 |
} |
| 130 |
} // namespace |
| 131 |
|
| 132 |
template <typename INT> |
| 133 |
void index_coord_sort(const std::vector<double> &xyz, std::vector<INT> &index, int axis) |
| 134 |
{ |
| 135 |
// For now, let's extract the component we want to sort on into a separate vector. |
| 136 |
std::vector<double> comp(xyz.size() / 3); |
| 137 |
size_t j = 0; |
| 138 |
for (size_t i = axis; i < xyz.size(); i += 3) { |
| 139 |
comp[j++] = xyz[i]; |
| 140 |
} |
| 141 |
exi_iqsort(Data(comp), Data(index), index.size()); |
| 142 |
} |
| 143 |
|
| 144 |
template <typename INT> void index_sort(const std::vector<INT> &ids, std::vector<INT> &index) |
| 145 |
{ |
| 146 |
index.resize(ids.size()); |
| 147 |
std::iota(index.begin(), index.end(), (INT)0); |
| 148 |
exi_iqsort(Data(ids), Data(index), index.size()); |
| 149 |
} |
| 150 |
|
| 151 |
template void index_coord_sort(const std::vector<double> &xyz, std::vector<int> &index, int axis); |
| 152 |
template void index_coord_sort(const std::vector<double> &xyz, std::vector<int64_t> &index, |
| 153 |
int axis); |
| 154 |
|
| 155 |
template void index_sort(const std::vector<int> &ids, std::vector<int> &index); |
| 156 |
template void index_sort(const std::vector<int64_t> &ids, std::vector<int64_t> &index); |