diff options
Diffstat (limited to 'test/mppa/sort/merge.c')
-rw-r--r-- | test/mppa/sort/merge.c | 92 |
1 files changed, 0 insertions, 92 deletions
diff --git a/test/mppa/sort/merge.c b/test/mppa/sort/merge.c deleted file mode 100644 index 99f8ba85..00000000 --- a/test/mppa/sort/merge.c +++ /dev/null @@ -1,92 +0,0 @@ -#include "../prng/prng.h" -#include "../prng/types.h" - -//https://en.wikipedia.org/wiki/Merge_sort - -#ifdef __UNIT_TEST_MERGE__ -#define SIZE 100 -#else -#include "test.h" -#endif - -int min(int a, int b){ - return (a < b)?a:b; -} - -void BottomUpMerge(const uint64_t *A, int iLeft, int iRight, int iEnd, uint64_t *B) -{ - int i = iLeft, j = iRight, k; - for (k = iLeft; k < iEnd; k++) { - if (i < iRight && (j >= iEnd || A[i] <= A[j])) { - B[k] = A[i]; - i = i + 1; - } else { - B[k] = A[j]; - j = j + 1; - } - } -} - -void CopyArray(uint64_t *to, const uint64_t *from) -{ - const int n = SIZE; - int i; - - for(i = 0; i < n; i++) - to[i] = from[i]; -} - -void BottomUpMergeSort(uint64_t *A, uint64_t *B) -{ - const int n = SIZE; - int width, i; - - for (width = 1; width < n; width = 2 * width) - { - for (i = 0; i < n; i = i + 2 * width) - { - BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B); - } - CopyArray(A, B); - } -} - -int merge_sort(uint64_t *res, const uint64_t *T){ - int i; - - if (SIZE <= 0) - return -1; - - uint64_t B[SIZE]; - uint64_t *A = res; - for (i = 0 ; i < SIZE ; i++) - A[i] = T[i]; - - BottomUpMergeSort(A, B); - - return 0; -} - -#ifdef __UNIT_TEST_MERGE__ -int main(void){ - uint64_t T[SIZE]; - uint64_t res[SIZE]; - int i; - srand(42); - - for (i = 0 ; i < SIZE ; i++) - T[i] = randlong(); - - /* Sorting the table */ - if (merge_sort(res, T) < 0) return -1; - - /* Computing max(T) */ - uint64_t max = T[0]; - for (i = 1 ; i < SIZE ; i++) - if (T[i] > max) - max = T[i]; - - /* We should have: max(T) == res[SIZE] */ - return !(max == res[SIZE-1]); -} -#endif // __UNIT_TEST_MERGE__ |