Quick sort algorithm

Question

Is this algorithm good or can I improve it?

 static void QuickSort(int[] a)
    {
        QuickSort(a, 0, a.Length - 1);
    }

    static void QuickSort(int[] a, int start, int end)
    {
        if (start >= end)
        {
            return;
        }

        int num = a[start];

        int i = start, j = end;

        while (i < j)
        {
            while (i < j && a[j] > num)
            {
                j--;
            }

            a[i] = a[j];

            while (i < j && a[i] < num)
            {
                i++;
            }

            a[j] = a[i];
        }

        a[i] = num;
        QuickSort(a, start, i - 1);
        QuickSort(a, i + 1, end);
    }

Answer 1

The algorithm is not readable. Usually, people cannot remember the quicksort in detail, even the code is written perfectly, people are still easily getting lost. Also, quicksort is kind of tricky, where to set pivot point, there is more than 1 choice. A few ideas to share:

1. For quicksort, it is very classical algorithm, better to make the code easy to read, like applying SRP - single responsibility principle, write a small function called partition.
2. Write a small function called swap().
3. Also, find a quicksort solution you like, and then write your own. Make the algorithm more readable, less mental challenge.
4. Write at least one test case to test the code.

Let me use my practice as an example: C# code I did:

  public static void quickSort(int[] A, int left, int right)
    {
        if(left > right || left <0 || right <0) return; 

        int index = partition(A, left, right);

        if (index != -1)
        {
            quickSort(A, left, index - 1);
            quickSort(A, index + 1, right);
        }
    }

    private static int partition(int[] A, int left, int right)
    {
        if(left > right) return -1; 

        int end = left; 

        int pivot = A[right];    // choose last one to pivot, easy to code
        for(int i= left; i< right; i++)
        {
            if (A[i] < pivot)
            {
                swap(A, i, end);
                end++; 
            }
        }

        swap(A, end, right);

        return end; 
    }

    private static void swap(int[] A, int left, int right)
    {
        int tmp = A[left];
        A[left] = A[right];
        A[right] = tmp; 
    }

References:

1. C# code

2. quicksort code reference

Answer 2

Though it is character-building to transform a recursive algorithm into an iterative form (and vice versa) I would not worry too much about iterative vs recursive.

There are several ways you could improve this code.

• As I said in your previous post: why an array? You could be much more general and sort an IList<int>. And why ints? You can sort any collection of things that can be compared consistently which would make your sorting algorithm more useful.

• start and end are very clear. i, j and num are not. How is the reader of this code supposed to understand what it does? Rename num to what it is: the pivot.

• Recursive quicksort has four basic steps: (1) decide if we're already sorted, (2) choose a pivot, (3) partition and (4) recurse. The considerable majority of your algorithm is devoted to (3). Consider putting the partition logic in a helper method that can be clearly shown to be correct.

• Consider showing us your test cases.

• There is no error handling; what if the array is null? What if the start and end are out of bounds? And so on.

• Consider adding postcondition assertions. A postcondition assertion is a Debug.Assert that documents what the method ensures is true just before it returns. In your case the postcondition is "the array is sorted from start to end". So assert that; write a little "is sorted" predicate and verify that it works. This will help you find bugs, if there are any. This will help future readers of the code understand it. And it will help people who change the code in the future understand what needs to not break when they modify the code.

• The partition step also has a postcondition; after the partition the array is partitioned into three parts: the values before the pivot are smaller or equal to it, the pivot, and the values after the pivot are greater than it. Assert that these conditions are met.

Answer 3

I've tried your algorithm with

int[] data = new [] { 17, 20, 11, 8, 0, 1, 14, 9, 9, 15, 5, 12, 8, 11, 16, 11, 11, 9, 16, 18 };

and it doesn't work. It loops infinitely in outer while-loop.

I could make it work as this:

public static void QuickSort(int[] a)
{
  QuickSort(a, 0, a.Length - 1);
}

static void QuickSort(int[] a, int start, int end)
{
  if (start >= end)
  {
    return;
  }

  int num = a[start];

  int i = start - 1;
  int j = end + 1;

  while (true)
  {
    do
    {
      i++;
    } while (a[i] < num);

    do
    {
      j--;
    } while (a[j] > num);

    if (i >= j)
      break;

    Swap(a, i, j);
  }

  //a[i] = num;
  QuickSort(a, start, j);
  QuickSort(a, j + 1, end);
}

static void Swap(int[] a, int i, int j)
{
  if (i == j)
    return;

  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

Take a look here for some background

Answer 4

Seems to me like you're on the right track, but the significant problem with your implementation is the fact that you're using recursion. Instead (to make it iterative), you should have one function that partitions your array, a small data structure to use as a pointer to walk across the array, and a function that performs the sorting. I started on my own solution, but found this one to be more descriptive. There are also plenty of other examples of other sorting methods linked to it that I hope will help.

Answer 5

Good of you to include an explicit question, if a compound one.

Is this algorithm good…?

This is quicksort, using Hoare's partition scheme with a twist (use two reads and two writes to resolve one inversion wrt. pivot instead of a swap (/"exchange" - making it the counterexample to labelling quicksort "partition-exchange sort": a direct exchange is not essential (partition is)), conventionally taken to be equivalent to three reads&writes, each. With today's memory hierarchies, don't expect it to be any faster because of this).
This is a respected algorithm in wide use, if with three-way-partition, even dual pivot values.
(There is a bug in your implementation: stuck if both i and j index an element equal to the pivot value (num).)

Can I improve [quicksort with minimised reads&writes in partition]?

For readability, you can and should separate the concerns of picking a pivot index, partition, and sort.
Of the Implementation issues mentioned in the wikipedia article, two reduce the likelihood and severity of worst case behaviour:

• don't pick a value close to the beginning or end of the range as a pivot - this is a bad choice with ordered input (even almost and/or reverse ordered).
• recurse on the partitions from smallest to largest - this should limit the growth in call stack depth to logarithmic in the number of items to sort thanks to "tail call"/"tail recursion" optimisation. (If it doesn't, options include picking a pivot that guarantees a favourable partition, or turning the call for the largest partition into iteration.)

(Getting late: the following code is work in progress; posting this to save the above, mainly (not quite trusting SE's autosave)(Never used C# - give me a break on documentation comments, const-correctness, commendable use of static or some such.))

    static int pivotIndex(int left, int right)
    {
        int n = right - left;
        return left + n/2;
    }
 /** partition int array a from start to end, exclusive
  *  @returns -1 if known sorted, else (one) index of pivot */
    static int partition(int[] a, int left, int right, int pivotIndex// = left
        ) {
        int l = left,
            r = right;

        int pivot = a[pivotIndex]; // a[pivotIndex] available for storage
        a[pivotIndex] = a[l]; // a[l] available for storage
        for (;;) {
            do
                if (--r <= l) {
                    a[l] = pivot;
                    return l;
                }
            while (pivot <= a[r]);
            a[l] = a[r]; // a[r] available for storage

            do
                if (r <= ++l) {
                    a[r] = pivot;
                    return r;
                }
            while (a[l] <= pivot);
            a[r] = a[l]; // a[l] available for storage
        }
    }

 /** sort int array a from start to end, exclusive */
    static void QuickSort(int[] a, int start, int end) {
        int pivotIndex = partition(a, start, end,
            pivotIndex(start, end));
        if (start < pivotIndex) {
            QuickSort(a, start, pivotIndex);
        //  QuickSort(a, pivotIndex + 1, end);
        } // else
        if (start <= pivotIndex)
            QuickSort(a, pivotIndex + 1, end);
    }