qsort.c 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137
  1. /*
  2. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  3. * See the copyright notice in the ACK home directory, in the file "Copyright".
  4. */
  5. /* $Header$ */
  6. #include <stdlib.h>
  7. static void qsort1(char *, char *, size_t);
  8. static int (*qcompar)(const char *, const char *);
  9. static void qexchange(char *, char *, size_t);
  10. static void q3exchange(char *, char *, char *, size_t);
  11. void
  12. qsort(void *base, size_t nel, size_t width,
  13. int (*compar)(const void *, const void *))
  14. {
  15. qcompar = (int (*)(const char *, const char *)) compar;
  16. qsort1(base, (char *)base + (nel - 1) * width, width);
  17. }
  18. static void
  19. qsort1(char *a1, char *a2, register size_t width)
  20. {
  21. register char *left, *right;
  22. register char *lefteq, *righteq;
  23. int cmp;
  24. for (;;) {
  25. if (a2 <= a1) return;
  26. left = a1;
  27. right = a2;
  28. lefteq = righteq = a1 + width * (((a2-a1)+width)/(2*width));
  29. /*
  30. Pick an element in the middle of the array.
  31. We will collect the equals around it.
  32. "lefteq" and "righteq" indicate the left and right
  33. bounds of the equals respectively.
  34. Smaller elements end up left of it, larger elements end
  35. up right of it.
  36. */
  37. again:
  38. while (left < lefteq && (cmp = (*qcompar)(left, lefteq)) <= 0) {
  39. if (cmp < 0) {
  40. /* leave it where it is */
  41. left += width;
  42. }
  43. else {
  44. /* equal, so exchange with the element to
  45. the left of the "equal"-interval.
  46. */
  47. lefteq -= width;
  48. qexchange(left, lefteq, width);
  49. }
  50. }
  51. while (right > righteq) {
  52. if ((cmp = (*qcompar)(right, righteq)) < 0) {
  53. /* smaller, should go to left part
  54. */
  55. if (left < lefteq) {
  56. /* yes, we had a larger one at the
  57. left, so we can just exchange
  58. */
  59. qexchange(left, right, width);
  60. left += width;
  61. right -= width;
  62. goto again;
  63. }
  64. /* no more room at the left part, so we
  65. move the "equal-interval" one place to the
  66. right, and the smaller element to the
  67. left of it.
  68. This is best expressed as a three-way
  69. exchange.
  70. */
  71. righteq += width;
  72. q3exchange(left, righteq, right, width);
  73. lefteq += width;
  74. left = lefteq;
  75. }
  76. else if (cmp == 0) {
  77. /* equal, so exchange with the element to
  78. the right of the "equal-interval"
  79. */
  80. righteq += width;
  81. qexchange(right, righteq, width);
  82. }
  83. else /* just leave it */ right -= width;
  84. }
  85. if (left < lefteq) {
  86. /* larger element to the left, but no more room,
  87. so move the "equal-interval" one place to the
  88. left, and the larger element to the right
  89. of it.
  90. */
  91. lefteq -= width;
  92. q3exchange(right, lefteq, left, width);
  93. righteq -= width;
  94. right = righteq;
  95. goto again;
  96. }
  97. /* now sort the "smaller" part */
  98. qsort1(a1, lefteq - width, width);
  99. /* and now the larger, saving a subroutine call
  100. because of the for(;;)
  101. */
  102. a1 = righteq + width;
  103. }
  104. /*NOTREACHED*/
  105. }
  106. static void
  107. qexchange(register char *p, register char *q,
  108. register size_t n)
  109. {
  110. register int c;
  111. while (n-- > 0) {
  112. c = *p;
  113. *p++ = *q;
  114. *q++ = c;
  115. }
  116. }
  117. static void
  118. q3exchange(register char *p, register char *q, register char *r,
  119. register size_t n)
  120. {
  121. register int c;
  122. while (n-- > 0) {
  123. c = *p;
  124. *p++ = *r;
  125. *r++ = *q;
  126. *q++ = c;
  127. }
  128. }