5
\$\begingroup\$

Code review my quicksort! It isn't supposed to be superfast or anything and doesn't basecase out to insertion sort or anything. It's optimized for clarity and only sorts arrays of pointers.

#define MISC_XCHG(a, b) ({ __typeof__(a) MISC_XCHG__A = (a); (a) = (b); (b) = MISC_XCHG__A; })

static void misc_qsort_internal(void const** A, void const** Z, bool (*cmp)(void const*, void const*))
{
  while ((Z - A) > 1) {
    /*
      quicksort is a bit tricky. the basic idea of just partitioning
      into < and >= partitions and recursing on each isn't guaranteed
      to terminate, because everything can end up in the >= part.

      the key to termination is to make sure at least one element
      drops out.

      the element that drops out must be equal to the pivot, so that
      it can be >= everything in the < part and <= to everything in
      the >= part. most simply, this element can be the pivot, which
      should be inserted between the < and the >= parts.

      so as we build up the regions we keep the pivot at the start of
      the array and later exchange it with the last element in the <
      part.
    */
    void const* pivot = *A;

    /* S points to the first element in the >= part */
    void const** S = A+1;

    for (void const** I = S; I < Z; I++) {
      if (cmp(*I, pivot)) {
        /* when *I < pivot */
        /* we must exchange with the first element in the >= part */
        MISC_XCHG(*I, *S);
        /* and shift the >= part over by one */
        S++;
      } else {
        /* when *I >= pivot */
        /* nothing to do, the >= part grows "automatically" */
      }
    }

    /* now do the business of exchanging the pivot */
    void const** R = (S - 1);
    *A = *R;
    *R = pivot;

    /* recursively sort (>=A, <R) and (>=S, <Z) */
    /* recurse on the smaller partition */
    /* this keeps stack usage always at or below O(log n) */
    if ((R - A) < (Z - S)) {
      misc_qsort_internal(A, R, cmp);
      A = S; /* loop to sort (>=S, <Z) */
    } else {
      misc_qsort_internal(S, Z, cmp);
      Z = R; /* loop to sort (>=A, <R) */
    }
  }
}

/*
  cmp should return true iff [arg1] < [arg2] (strictly).
*/
static INLINE void misc_qsort(void const** A, uintptr_t L, bool (*cmp)(void const*, void const*))
{
  misc_qsort_internal(A, (A + L), cmp);
}

#define MISC_QSORT_VARIANT(s, t)                                        \
  static INLINE void misc_qsort_##s(t** A, uintptr_t L, bool (*cmp)(t const*, t const*)) \
  {                                                                     \
    misc_qsort(((void const**)(A)), L, ((bool (*)(void const*, void const*))(cmp))); \
  }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.