Laboratory Rubric : Structure : Factoring

CSC 213 - Operating Systems and Parallel Algorithms - Weinman

Summary:: We describe what it means for a program to be factored into appropriate functions.

Good

The distinctions between Excellent and Passing programs are more likely to be differences of degree than differences in kind. That said, let us examine a simple Quicksort example, whose primary code is taken from Kernighan and Pike [KP, p. 33]

: /* quicksort: sort v[0]..v[n-1] into increasing order */
void quicksort (int v[], int n)
{
  int i, last;

  if (n <= 1) /* nothing to do */
    return;
  swap(v, 0, rand() % n); /* move pivot elem to v[0] */
  last = 0;
  for (i = 1; i < n; i++) /* partition */
    if (v[i] < v[0])
      swap(v, ++last, i);
  swap(v, 0, last);       /* restore pivot */
  quicksort(v, last);     /* recursively sort */
  quicksort(v+last+1, n-last-1); /* each part */
}

If you're not familiar with the quick sort algorithm, you might notice how relatively straightforward this algorithm is to read (with likely the exception of the partitioning loop). Much of that is due to the fact that the thrice-repeated swap function has been factored out.

: /* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
  int temp;

  temp = v[i];
  v[i] = v[j];
  v[j] = temp;
}

This program would receive Good marks; it's debatable whether factoring out the partitioning, even though it is only used once, improve the clarity (and testability) of the final result.

Excellent

Let's try partitioning Kernighan and Pike's partition (so to speak).

: /* quicksort: sort v[0]..v[n-1] into increasing order */
void quicksort (int v[], int n)
{
  int i, last;

  if (n <= 1) /* nothing to do */
    return;
  swap(v, 0, rand() % n); /* move pivot elem to v[0] */
  last = partition(v,n);  /* partition and get boundary */
  swap(v, 0, last);       /* restore pivot */
  quicksort(v, last);     /* recursively sort */
  quicksort(v+last+1, n-last-1); /* each part */
}

While the added "partition" comment is somewhat redundant, omitting it seems incomplete. The new function necessarily looks like:

: /* partition: rearrange v and return last so that
*              v[i] <  v[0] for 0<i<=last and
*              v[i] >= v[0] for i>last. */
int partition(v, n)
{
  int last = 0;
  for (i = 1; i < n; i++) /* partition */
    if (v[i] < v[0])
      swap(v, ++last, i);
  return last;
}

Notice how the the main sort routine is easier to read and the explicit postconditions of partition are easy to test. We debated moving the two swap calls immediately preceding and following the call to partition directly into partition itself. The latter swap would make the postconditions more straightforward. The compound effect of moving both would do little to make the partition algorithm clearer, though the quicksort function is perhaps clarified through greater brevity. The advantage of the version presented is that it leaves room to add yet another function that chooses the pivot (leaving it in v[0]), which turns out to have important impacts on effiency.

As another example, a large scale parsing problem from the author's PhD dissertation featured five nested four loops. Good factorization meant each loop was broken out into its own function.

Passing

For completeness, let us see how hard it is to understand a function does not factor out the swap operation.

: /* quicksort: sort v[0]..v[n-1] into increasing order */
void quicksort (int v[], int n)
{
  int i, j, last, temp;

  if (n <= 1) /* nothing to do */
    return;

  j = rand() % n;  /* move pivot elem to v[0] */
  temp = v[0];
  v[0] = v[j];
  v[j] = temp;

  last = 0;
  for (i = 1; i < n; i++) /* partition */
    if (v[i] < v[0])
    {
      last++;
      temp = v[last];     /* swap last, i */
      v[last] = v[i];
      v[i] = temp;
    }
  temp = v[0];       /* restore pivot */
  v[0] = v[last];
  v[last] = v[tmp];
  quicksort(v, last);     /* recursively sort */
  quicksort(v+last+1, n-last-1); /* each part */
}

The only saving grace here is the fact that quicksort remains defined recursively. We won't even deign to show you an iterative version.

References

[KP]: Brian W. Kernighan and Rob Pike. The Practice of Programming. Addison-Wesley, 1999.

This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.