C# QuickSort recursive program not sorting

Question

I am trying to understand a quicksort example. I randomly generate 9 numbers and place in a list. The program selects a random pivot. Based on the pivot, the other values in the list are placed into the left list or right list. Then I call the method again using left list and right. This is where I get confused. It doesn't completely sort the 9 numbers. What am I doing wrong?

Here is my updated code. Now, if a pivot number is the same as another number in the list, it is not included in the sorted list when return e.g. unsorted 487878146, sorted 14678 The piece of code that I think is causing the issue is (if (j == pivot) continue;)

public static List<int> QuickSort(List<int> arr)
    {
        Random random = new Random();
        int i, pivot;

        List<int> leftList = new List<int>();
        List<int> rightList = new List<int>();

        if (arr.Count > 1)
        {
            //pivot = random.Next(arr[0],arr[arr.Count - 1]);
            pivot = arr[random.Next(0, arr.Count - 1)];
                foreach(int j in arr)
                {
                    if (j == pivot) continue;
                    if (j <= pivot)
                        leftList.Add(j);
                    else
                        rightList.Add(j);
                }

            List<int> sortedLeft = QuickSort(leftList);
            List<int> sortedRight = QuickSort(rightList);

            List<int> tempList = new List<int>();
            tempList.AddRange(sortedLeft);
            tempList.Add(pivot);
            tempList.AddRange(sortedRight);

            //for (i = 1; i <= leftList.Count; i++)
            //    tempList.Add(leftList[i - 1]);
            //tempList.Add(pivot);
            //for (i = 1; i <= rightList.Count; i++)
            //    tempList.Add(rightList[i - 1]);


            return tempList;
        }
        return arr;
    }

You should not create multiple Random objects. Create one and reuse it. Though here it is probably not related to your actual problem. — Mark Byers
– Mark Byers, Commented Oct 8, 2012 at 18:06
Please debug your code yourself first... There was also solution to the same problem earlier today to compare - stackoverflow.com/questions/12785824/… — Alexei Levenkov
– Alexei Levenkov, Commented Oct 8, 2012 at 18:07
this doesn't really look like quicksort at all. This looks like mergesort but without the merge, and not quite cutting each segment exactly in half. — Servy
– Servy, Commented Oct 8, 2012 at 18:08
Also, isn't the one of the strong points of quicksort being able to sort in place, rather than using temporary lists? — Wug
– Wug, Commented Oct 8, 2012 at 18:09
Your selection of the pivot won't always be an item in the list. Rather than a random number between max and min, take a random index between 0 and the list size and use the item at that index. (or, for simplicity, just use the first item). — Servy
– Servy, Commented Oct 8, 2012 at 18:12

Lee · Accepted Answer · 2012-10-08 18:08:29Z

2

Your quicksort returns the sorted list, so you need to merge them instead of the unsorted inputs:

List<int> sortedLeft = QuickSort(leftList);
List<int> sortedRight QuickSort(rightList);

List<int> tempList = new List<int>();
tempList.AddRange(sortedLeft);
tempList.Add(pivot);
tempList.AddRange(sortedRight);

answered Oct 8, 2012 at 18:08

Lee

145k20 gold badges243 silver badges292 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Nikola Davidovic · Accepted Answer · 2012-10-08 18:30:14Z

0

In addition to Lee's answer, you should modify your pivot selection because you are using random number that doesn't have to be in the array and then insert it in a list. You can try for instance something like this:

pivot = arr[random.Next(0,arr.Length - 1)];

answered Oct 8, 2012 at 18:30

Nikola Davidovic

8,6761 gold badge31 silver badges34 bronze badges

3 Comments

Colin Roe Over a year ago

Thanks,I updated my code. Now, if a pivot number is the same as another number in the list, it is not included in the sorted list when returned e.g. unsorted 487878146, sorted 14678 The piece of code that I think is causing the issue is (if (j == pivot) continue;)

Nikola Davidovic Over a year ago

Yes,but you can include j element in any list you want. For instance,instead of continue,put in a leftList.

Colin Roe Over a year ago

I tried and got a StackOverflow exception. What I did was count the amount of times the j element is equal to the pivot. Then when I merge the lists, I add the pivot, n amount of times to the list based on the count. It works.

Collectives™ on Stack Overflow

C# QuickSort recursive program not sorting

2 Answers 2

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related