qsort.c 3.0 KB

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