| 1 |
/* |
| 2 |
* Copyright(C) 1999-2020, 2022 National Technology & Engineering Solutions |
| 3 |
* of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with |
| 4 |
* NTESS, the U.S. Government retains certain rights in this software. |
| 5 |
* |
| 6 |
* See packages/seacas/LICENSE for details |
| 7 |
*/ |
| 8 |
#pragma once |
| 9 |
#include <climits> |
| 10 |
|
| 11 |
template <typename T> inline void my_swap(T &r, T &s) |
| 12 |
{ |
| 13 |
T tmp = r; |
| 14 |
r = s; |
| 15 |
s = tmp; |
| 16 |
} |
| 17 |
|
| 18 |
template <typename T, typename U> void siftDown(T *a, U *b, int64_t start, int64_t end) |
| 19 |
{ |
| 20 |
int64_t root = start; |
| 21 |
|
| 22 |
while (root * 2 + 1 < end) { |
| 23 |
int64_t child = 2 * root + 1; |
| 24 |
if ((child + 1 < end) && (a[child] < a[child + 1])) { |
| 25 |
child += 1; |
| 26 |
} |
| 27 |
if (a[root] < a[child]) { |
| 28 |
my_swap(a[child], a[root]); |
| 29 |
my_swap(b[child], b[root]); |
| 30 |
root = child; |
| 31 |
} |
| 32 |
else { |
| 33 |
return; |
| 34 |
} |
| 35 |
} |
| 36 |
} |
| 37 |
|
| 38 |
template <typename T, typename U> void my_sort(int64_t count, T ra[], U rb[]) |
| 39 |
{ |
| 40 |
int64_t start, end; |
| 41 |
|
| 42 |
/* heapify */ |
| 43 |
for (start = (count - 2) / 2; start >= 0; start--) { |
| 44 |
siftDown(ra, rb, start, count); |
| 45 |
} |
| 46 |
|
| 47 |
for (end = count - 1; end > 0; end--) { |
| 48 |
my_swap(ra[end], ra[0]); |
| 49 |
my_swap(rb[end], rb[0]); |
| 50 |
siftDown(ra, rb, 0, end); |
| 51 |
} |
| 52 |
} |
| 53 |
|
| 54 |
/*****************************************************************************/ |
| 55 |
/*****************************************************************************/ |
| 56 |
/*****************************************************************************/ |
| 57 |
extern void print_line(const char *charstr, int ntimes); |