current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 1 down vote favorite
1

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);
    }
share|improve this question
    
The major issue which i see is recursion. Try to write a nonrecursive version of the same. – Balraj Singh 2 days ago
1  
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). – Jesse C. Slicer 2 days ago
    
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.) – greybeard 11 hours ago
up vote 1 down vote accepted

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

share|improve this answer
up vote 5 down vote

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.

share|improve this answer
    
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. – Moder 2 days ago
up vote 2 down vote

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.

share|improve this answer
    
It helped a lot thank you – Moder 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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