C# Quicksort Assignment

Question

For my CS minor I was assigned to implement the Quicksort algorithm in C#. I gave it a go and found that I like the implementation of the algorithm more than Mergesort. Now that I've got my Quicksort implementation running, I'm very curious about what optimizations could be done.

using System.Collections.Generic;

namespace Assignment
{
    public class QuickSort
    {
        public void Sort(List<int> list)
        {
            if (list.Count <= 1)
            {
                return;
            }

            int pivot = MedianOfThree(list);
            int equalElementCount = 0;

            List<int> smaller = new List<int>();
            List<int> bigger = new List<int>();

            for (int i = 0; i < list.Count; i++)
            {
                if (list[i] == pivot)
                {
                    equalElementCount++;
                }
                else if (list[i] < pivot)
                {
                    smaller.Add(list[i]);
                }
                else
                {
                    bigger.Add(list[i]);
                }
            }

            Sort(smaller);
            Sort(bigger);

            int pointer = 0;
            for (int i = 0; i < smaller.Count; i++)
            {
                list[pointer++] = smaller[i];
            }
            for (int i = 0; i < equalElementCount; i++)
            {
                list[pointer++] = pivot;
            }
            for (int i = 0; i < bigger.Count; i++)
            {
                list[pointer++] = bigger[i];
            }
        }

        private int MedianOfThree(List<int> list)
        {
            int firstElement = list[0];
            int middleElement = list[list.Count / 2];
            int lastElement = list[list.Count - 1];

            if ((firstElement > middleElement) != (firstElement > lastElement))
            {
                return firstElement;
            }
            else if ((middleElement > firstElement) != (middleElement > lastElement))
            {
                return middleElement;
            }
            else
            {
                return lastElement;
            }
        }
    }
}

Answer 1

Over the years I have seen other students here and they are quite proud of the performance of their code. In some of those past instances I have discovered that they had simply run their code and thought it was fast. They did not compare it to other methods.

You don't mention any testing or provide any numbers. If you were to do this, just be sure that (1) your code is a Release build and not a Debug, and (2) that you do have disabled "Prefer 32-bit" for Build.

The biggest thing that strikes me about your implementation versus others I have seen is that you make 2 lists (smaller and bigger) per invocation whereas other implementations perform an in-place sort on the list or array.

Does this matter?

YES. Performance is significantly faster when performing in-place sorting using the one list.

I wrote a sample for you. I have decide not to post my code here because you are a CS student and your namespace is Assignment which tells me this is classwork. It would be unethical of me to write this code for you. What I will do instead you point you to the resources I used, and show my performance timings.

My reference was Wikipedia Quicksort. In particular I used the Hoare partition scheme. I translated the psuedocode to C#.

I will share key method signatures. Yes, plural.

public static void Sort2(List<int> list) => Sort2(list, 0, list.Count - 1);

private static void Sort2(List<int> list, int lowIndex, int highIndex)
{
    // Good luck on your assignment!
}

I also had a Partition and Swap method. I leave it to you to decide whether these should be public or private and what they do.

PERFORMANCE

• Size of list: 10_000

• Number of trials: 10_000

• Original QuickSort ElapsedTicks: 117_816_477

• In-place QuickSort ElapsedTicks: 50_171_790

Which means your original is 2.3 times slower than my in-place sorting.