sort-test.c 1.9 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5. #include "puzzles.h"
  6. static int testcmp(const void *av, const void *bv, void *ctx)
  7. {
  8. int a = *(const int *)av, b = *(const int *)bv;
  9. const int *keys = (const int *)ctx;
  10. return keys[a] < keys[b] ? -1 : keys[a] > keys[b] ? +1 : 0;
  11. }
  12. static int resetcmp(const void *av, const void *bv)
  13. {
  14. int a = *(const int *)av, b = *(const int *)bv;
  15. return a < b ? -1 : a > b ? +1 : 0;
  16. }
  17. int main(int argc, char **argv)
  18. {
  19. typedef int Array[3723];
  20. Array data, keys;
  21. int iteration;
  22. unsigned seed;
  23. seed = (argc > 1 ? strtoul(argv[1], NULL, 0) : time(NULL));
  24. printf("Random seed = %u\n", seed);
  25. srand(seed);
  26. for (iteration = 0; iteration < 10000; iteration++) {
  27. int j;
  28. const char *fail = NULL;
  29. for (j = 0; j < lenof(data); j++) {
  30. data[j] = j;
  31. keys[j] = rand();
  32. }
  33. arraysort(data, lenof(data), testcmp, keys);
  34. for (j = 1; j < lenof(data); j++) {
  35. if (keys[data[j]] < keys[data[j-1]])
  36. fail = "output misordered";
  37. }
  38. if (!fail) {
  39. Array reset;
  40. memcpy(reset, data, sizeof(data));
  41. qsort(reset, lenof(reset), sizeof(*reset), resetcmp);
  42. for (j = 0; j < lenof(reset); j++)
  43. if (reset[j] != j)
  44. fail = "output not permuted";
  45. }
  46. if (fail) {
  47. printf("Failed at iteration %d: %s\n", iteration, fail);
  48. printf("Key values:\n");
  49. for (j = 0; j < lenof(keys); j++)
  50. printf(" [%2d] %10d\n", j, keys[j]);
  51. printf("Output sorted order:\n");
  52. for (j = 0; j < lenof(data); j++)
  53. printf(" [%2d] %10d\n", data[j], keys[data[j]]);
  54. return 1;
  55. }
  56. }
  57. printf("OK\n");
  58. return 0;
  59. }