1 /* Test of stable-sorting of an array using mergesort.
2 Copyright (C) 2009, 2010 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"
32 static const struct foo data[NMAX] =
294 cmp_double (const void *a, const void *b)
296 return (*(const double *)a < *(const double *)b ? -1 :
297 *(const double *)a > *(const double *)b ? 1 :
306 /* Test merge_sort_fromto. */
307 for (n = 1; n <= NMAX; n++)
311 double *qsort_result;
314 dst = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
315 dst[n].x = 0x4A6A71FE; /* canary */
316 tmp = (struct foo *) malloc ((n / 2 + 1) * sizeof (struct foo));
317 tmp[n / 2].x = 0x587EF149; /* canary */
319 merge_sort_fromto (data, dst, n, tmp);
321 /* Verify the canaries. */
322 ASSERT (dst[n].x == 0x4A6A71FE);
323 ASSERT (tmp[n / 2].x == 0x587EF149);
325 /* Verify the result. */
326 qsort_result = (double *) malloc (n * sizeof (double));
327 for (i = 0; i < n; i++)
328 qsort_result[i] = data[i].x;
329 qsort (qsort_result, n, sizeof (double), cmp_double);
330 for (i = 0; i < n; i++)
331 ASSERT (dst[i].x == qsort_result[i]);
333 /* Verify the stability. */
334 for (i = 0; i < n; i++)
335 if (i > 0 && dst[i - 1].x == dst[i].x)
336 ASSERT (dst[i - 1].index < dst[i].index);
343 /* Test merge_sort_inplace. */
344 for (n = 1; n <= NMAX; n++)
348 double *qsort_result;
351 src = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
352 src[n].x = 0x4A6A71FE; /* canary */
353 tmp = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
354 tmp[n].x = 0x587EF149; /* canary */
356 for (i = 0; i < n; i++)
359 merge_sort_inplace (src, n, tmp);
361 /* Verify the canaries. */
362 ASSERT (src[n].x == 0x4A6A71FE);
363 ASSERT (tmp[n].x == 0x587EF149);
365 /* Verify the result. */
366 qsort_result = (double *) malloc (n * sizeof (double));
367 for (i = 0; i < n; i++)
368 qsort_result[i] = data[i].x;
369 qsort (qsort_result, n, sizeof (double), cmp_double);
370 for (i = 0; i < n; i++)
371 ASSERT (src[i].x == qsort_result[i]);
373 /* Verify the stability. */
374 for (i = 0; i < n; i++)
375 if (i > 0 && src[i - 1].x == src[i].x)
376 ASSERT (src[i - 1].index < src[i].index);