4
\$\begingroup\$

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);
    }
\$\endgroup\$
  • \$\begingroup\$ The major issue which i see is recursion. Try to write a nonrecursive version of the same. \$\endgroup\$ – Balraj Singh Sep 29 '16 at 14:50
  • 1
    \$\begingroup\$ Sure, on the performance side, introduce parallel processing to take advantage of additional CPUs/threads. Also, possibly choosing a better pivot than int num = a[start] could yield better performance (I believe most QS implementations choose the center element, which does excellently for already-sorted [or near sorted] data). \$\endgroup\$ – Jesse C. Slicer Sep 29 '16 at 16:20
  • \$\begingroup\$ You present uncommented source code. What is the idea with a[i] = a[j]; while (i < j && a[i] < num) i++; a[j] = a[i]; instead of the conventional swap? Does this code work, as required for CR? (It almost does: the minimal change required is the inclusion of values equal to the pivot in at least one of the conditions in the loop.) \$\endgroup\$ – greybeard Oct 1 '16 at 21:40
  • \$\begingroup\$ Did you come up with this variant of Hoare's partition on your own (see 2nd question to "Simply ask yourself")? If not, by all means credit/link properly. I haven't seen this in quite a while, and can't seem to find it from a non-Asian source?! \$\endgroup\$ – greybeard Oct 2 '16 at 19:56
  • \$\begingroup\$ I wrote a blog about quicksort to document my practice on the algorithm. Here is the link: juliachencoding.blogspot.ca/2016/02/… I will put short version with this comment later, in short future. \$\endgroup\$ – Jianmin Chen Nov 25 '16 at 6:56
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Can you try to point out which part of hard to read (understand, get correct/test/prove/maintain)(not readable) is due to this implementation (e.g., helpful comments, including a reference for unusual approaches), and what is intrinsic to the algorithm? Suggesting to write a function swap() is weird as the very point of the modification to the original algorithm (Hoare partitioning) is to use fewer memory accesses than the better known/previous schemes. Speaking of which: how do you compare, in terms of (not) readable, the Lomuto and Hoare partitioning schemes? \$\endgroup\$ – greybeard Nov 25 '16 at 9:46
  • \$\begingroup\$ @greybeard, I read the post codereview.stackexchange.com/a/77788/123986, and the code is also very readable. Partition function code can be read this way, there is no swap, and then, there is the first swap followed with a partition. You read the code and see if it is very clear or not. \$\endgroup\$ – Jianmin Chen Nov 26 '16 at 3:41
  • \$\begingroup\$ Please state unambiguously which code you are referring to. (The code on ideone that answer to a separate questions links to?) Which partition function can be read the way you put into words? What use is discussing some code neither in this question nor in your above answer to it in comments to your answer? \$\endgroup\$ – greybeard Nov 26 '16 at 5:17
  • \$\begingroup\$ int partition(int *arr, const int left, const int right) { const int mid = left + (right - left) / 2; const int pivot = arr[mid]; // move the mid point value to the front. std::swap(arr[mid],arr[left]); int i = left + 1; int j = right; while (i <= j) { while(i <= j && arr[i] <= pivot) { i++; } while(i <= j && arr[j] > pivot) { j--; } if (i < j) { std::swap(arr[i], arr[j]); } } std::swap(arr[i - 1],arr[left]); return i - 1; } \$\endgroup\$ – Jianmin Chen Nov 26 '16 at 5:19
  • 1
    \$\begingroup\$ You don't need to test the return value of partition, because you bail out of quickSort with the same test \$\endgroup\$ – Caleth May 3 at 15:58
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I choose an array because a list is basicly a wrapper of an array. I know I can sort anything I just chose this as a example. \$\endgroup\$ – Fire the Bullet Sep 29 '16 at 21:34
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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);
    }
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.