1 /* Test of stable-sorting of an array using mergesort.
2 Copyright (C) 2009 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify it
5 under the terms of the GNU Lesser General Public License as published
6 by the Free Software Foundation; either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
14 You should have received a copy of the GNU Lesser General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
21 struct foo { double x; double index; };
22 #define ELEMENT struct foo
23 #define COMPARE(a,b) ((a)->x < (b)->x ? -1 : (a)->x > (b)->x ? 1 : 0)
25 #include "array-mergesort.h"
30 #define ASSERT(expr) \
35 fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
43 static const struct foo data[NMAX] =
305 cmp_double (const void *a, const void *b)
307 return (*(const double *)a < *(const double *)b ? -1 :
308 *(const double *)a > *(const double *)b ? 1 :
317 /* Test merge_sort_fromto. */
318 for (n = 1; n <= NMAX; n++)
322 double *qsort_result;
325 dst = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
326 dst[n].x = 0x4A6A71FE; /* canary */
327 tmp = (struct foo *) malloc ((n / 2 + 1) * sizeof (struct foo));
328 tmp[n / 2].x = 0x587EF149; /* canary */
330 merge_sort_fromto (data, dst, n, tmp);
332 /* Verify the canaries. */
333 ASSERT (dst[n].x == 0x4A6A71FE);
334 ASSERT (tmp[n / 2].x == 0x587EF149);
336 /* Verify the result. */
337 qsort_result = (double *) malloc (n * sizeof (double));
338 for (i = 0; i < n; i++)
339 qsort_result[i] = data[i].x;
340 qsort (qsort_result, n, sizeof (double), cmp_double);
341 for (i = 0; i < n; i++)
342 ASSERT (dst[i].x == qsort_result[i]);
344 /* Verify the stability. */
345 for (i = 0; i < n; i++)
346 if (i > 0 && dst[i - 1].x == dst[i].x)
347 ASSERT (dst[i - 1].index < dst[i].index);
354 /* Test merge_sort_inplace. */
355 for (n = 1; n <= NMAX; n++)
359 double *qsort_result;
362 src = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
363 src[n].x = 0x4A6A71FE; /* canary */
364 tmp = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
365 tmp[n].x = 0x587EF149; /* canary */
367 for (i = 0; i < n; i++)
370 merge_sort_inplace (src, n, tmp);
372 /* Verify the canaries. */
373 ASSERT (src[n].x == 0x4A6A71FE);
374 ASSERT (tmp[n].x == 0x587EF149);
376 /* Verify the result. */
377 qsort_result = (double *) malloc (n * sizeof (double));
378 for (i = 0; i < n; i++)
379 qsort_result[i] = data[i].x;
380 qsort (qsort_result, n, sizeof (double), cmp_double);
381 for (i = 0; i < n; i++)
382 ASSERT (src[i].x == qsort_result[i]);
384 /* Verify the stability. */
385 for (i = 0; i < n; i++)
386 if (i > 0 && src[i - 1].x == src[i].x)
387 ASSERT (src[i - 1].index < src[i].index);