C# Quicksort an array with reoccurring values

Question

I have this problem with quicksort which works fine until I get one or more reoccurring values.

This problem seems to be known for quite some time and I have found several "solutions" and discussions on fora. The closest thing to an actual solution found is here: Quicksort infinite loop if there are repeating values The thing is I can't comment on that answer else I would.

But to get back to my question. How can I make this code work with reoccurring values. (and yes I know creating a swap method and a partition method might look nicer, but that is irrelevant to the question)

    public void QuickSort(int[] A, int lo, int hi)
    {
        if (lo < hi)
        {
            int pivot = A[(hi-lo)/2+lo]; // I can create a random pivot, but that has the same effect as putting the pivot in the middle. The sorting algorithm doesn't know the values.
            int left = 0;
            int right = hi;
            while (left <= right)
            {
                while (A[left] < pivot)
                    left++;
                while (A[right] > pivot)
                    right--;
                if (left <= right)
                {
                    int temp = A[left];
                    A[left] = A[right];
                    A[right] = temp;
                    left++;
                    right--;
                }
            }
            QuickSort(A, lo, right);
            QuickSort(A, left, hi);
        }
    }

Unless you are doing this to learn sorting algorithms, you should be using built in `Sort` or LINQ to do your sorting and ordering of data. — crashmstr, Sep 08 '14 at 13:13
`int left = 0;` is wrong - it should be `int left = lo;`. Otherwise, I see no immediate issues. — 500 - Internal Server Error, Sep 08 '14 at 13:18

score 0 · Accepted Answer · answered Sep 08 '14 at 13:33

It seems that your method doesn't start at the good index. Starting at loand not 0 will be better.

public void QuickSort(int[] A, int lo, int hi)
{
    if (lo < hi)
    {
        int pivot = A[(hi-lo)/2+lo]; // I can create a random pivot, but that has the same effect as putting the pivot in the middle. The sorting algorithm doesn't know the values.
        int left = lo;
        int right = hi;
...
    }
}

C# Quicksort an array with reoccurring values

1 Answers1