A simple trick to gain some optimization in your code

I see some times developers do not optimize recursive functions to put less load on stack although many times it can be done with some simple changes in the code without even affecting usability. Lets assume we have a recursive function like the following (which is a C# implementation of the Wikipedia version mentioned here):

public void QuickSort(int[] array, int left, int right) {
  If (left < right) {
    int pivot = Partition(array, left, right);
    QuickSort(array, left, pivot - 1);
    QuickSort(array, pivot + 1, right);
  }
}

To reduce the call stack depth change the if to while and instead of second recursive call to QuickSort change the left index like this:

public void QuickSort(int[] array, int left, int right) {
  while(left < right) {
      int pivot = Partition(array, left, right);
      QuickSort(array, left, pivot - 1);
      left = pivot + 1;
  }
}

Some compilers (e.g. F#) detect and optimize these kind of calls in recursive function (tail recursion), but C# is not one of them. IMHO these kind of optimizations are the responsibility of the developer and compiler needs to focus on many different type of optimizations.
Before I forget and just to be complete, here is the the implementation of Partition function:

private int Partition(int[] array, int left, int right, int pivot){
  int pivotValue = array[pivot];

  // Move pivot to the end of the array
  Swap(array, pivot, right);

  int sortIndex = left;

  for (int i = left; i < right; i++) {
    if (array[i] < pivotValue) {
      Swap(array, i, sortIndex);
      sortIndex++;
    }
  }

  // Move pivot its new place
  Swap(array, sortIndex, right);

  return sortIndex;
}
Advertisements
A simple trick to gain some optimization in your code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s