Quicksort & Quickselect

quick.c

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

static inline int
rand_in_range (int l, int u)
{
  assert (l <= u);
  int r=(random () % (u-l+1)) + l;
  assert (l <= r && r <= u);
  return r;
}

static inline void
swap (int *a, unsigned i, unsigned j)
{
  int t;
  t=a[i]; a[i]=a[j]; a[j]=t;
}

void
insertion_sort (int *a, unsigned n)
{
  int t;
  unsigned i, j;
  for (i=1; i<n; i++)
    {
      t=a[i];
      for (j=i; j>0 && a[j-1]>t; j--)
        a[j]=a[j-1];
      a[j]=t;
    }
}

/* Two-sided partitioning from page 120 with loop invariant:

     +---+-------+-----+-------+
     | t |  <=t  |  ?  |  >=t  |
     +---+-------+-----+-------+
*/
static inline unsigned
partition (int *a, unsigned m, int l, int u)
{
  assert (l <= m && m <= u);
  swap (a, m, l);
  int t=a[l];
  unsigned i=l, j=u+1;
  while (true)
    {
      do i++; while (i<=u && a[i]<t);
      do j--; while (j>l && a[j]>=t);
      if (i>j)
        break;
      swap (a, i, j);
    }
  swap (a, l, j);
  return j;
}

void
quicksort (int *a, int l, int u)
{
  if (l >= u)
    return;
  unsigned m=partition (a, rand_in_range (l, u), l, u);
  quicksort (a, l, m-1);
  quicksort (a, m+1, u);
}

int
quickselect_recursive (int *a, unsigned k, int l, int u)
{
  assert (l < k && k <= u+1);
  k--;
  if (l >= u)
    return a[l];
  unsigned m=partition (a, rand_in_range (l, u), l, u);
  if (k==m)
    return a[m];
  else if (k>m)
    return quickselect_recursive (a, ++k, m+1, u);
  else
    return quickselect_recursive (a, ++k, l, m-1);
}

int
quickselect (int *a, unsigned k, int l, int u)
{
  assert (l < k && k <= u+1);
  k--;
  if (l==u)
    return a[l];
  unsigned m;
  while (true)
    {
      m=partition (a, rand_in_range (l, u), l, u);
      if (k==m)
        return a[m];
      else if (k>m)
        l=m+1;
      else
        u=m-1;
    }
}

bool
partition_invariant_holds (int *a, int m, unsigned n)
{
  unsigned i;
  for (i=0; i<n; i++)
  if (a[i]>m)
    break;
  for (; i<n; i++)
  if (a[i]<m)
    return false;
  return true;
}

bool
is_sorted (int *a, unsigned n)
{
  unsigned i;
  for (i=1; i<n; i++)
    if (a[i-1]>a[i])
      return false;
  return true;
}

void
print_array (int *a, unsigned n)
{
  unsigned i;
  for (i=0; i<n; i++)
    printf ("%d ", a[i]);
  printf ("\n");
}

int
main (int argc, char **argv)
{
  unsigned n=6, i=n/2+1;
  int j, a[] = {1, 3, 2, 4, 3, 5};

  printf ("input:\n  ");
  print_array (a, n);

  j=quickselect (a, i, 0, n-1);
  printf ("\nquickselect: %u-th smallest element of `a` equals %d.\n  ", i, j);
  print_array (a, n);
  assert (partition_invariant_holds (a, j, n));

  quicksort (a, 0, n-1);
  printf ("\nquicksort:\n  ");
  print_array (a, n);
  assert (j==a[i-1]);
  assert (is_sorted (a, n));

  return 0;
}