Why is my Bubblesort implementation faster than my Quicksort code? [closed]

Question

Here is my Bubblesort code:

public static List<int> BubbleSort(List<int> _digitList)
      {
          List<int> digitList = _digitList;
          bool didSwap = true;

          while (didSwap)
          {
                didSwap = false;
                for (int i = 0; i < digitList.Count - 1; i++)
                {                    
                    if (digitList[i] > digitList[i + 1])
                    {
                        int temp = digitList[i];
                        digitList[i] = digitList[i + 1];
                        digitList[i + 1] = temp;

                        didSwap = true;
                    }
                }
          }
          return digitList;
      }

And here is my Quicksort Method, which is actually an implementation of the pseudocode on Wikipedia:

public static List<int> Quicksort(List<int> array)
        {
            if (array.Count <= 1)
            {
                return array; //An array of Zero ot one elements is already sorted
            }

            int pivot = 0;
            List<int> less = new List<int>();
            List<int> greater = new List<int>();

            for (int i = 1; i < array.Count;i++ )
            {
                if (array[i] <= array[pivot])
                {
                    less.Add(array[i]);
                }
                else
                {
                    greater.Add(array[i]);
                }
            }

            List<int> combined = Quicksort(less);
            combined.Add(array[pivot]);
            combined.AddRange(Quicksort(greater));

            return combined;

        }

So for the List = {211, 16, 42, 166, 192, 2, 13, 81, 6, 1, 5, 115, 17, 67}; I get following Stopwatch values.

Bubblesort:

00:00:00.0002873

Quicksort:

00:00:00.0003831

Does this mean my Quicksort code is poor or did I misunderstand the Stopwatch concept?

Answer 1

It is normal in production quality qsort code to switch to another sorting method (maybe a unrolled bubble sort) when the size of the input is small (often 8 is used). QSort has very high overheads, but scales well, for a small input size the overheads are much more important than the scaling.

If you run your code on an input that is 1000 items long, then I expect that your qsort would be faster than your bubble sort.

Try writing a test problem that increases your input size in steps of 100 and then graph the results with both sorting methods.

The other way to look at it, is to find the largest input that each sort method can sort in say 5 seconds.

---

---

Also your qSort could be written to be a lot faster by not creating 3 new Lists, it is also very important to quickly choose a good item to privet on. You do not even set the size of the list when you create them, hence each list will have to be reallocated and copied many times as you add items to it.

You have a qSort that is implemented is an inefficient way compared to a boubleSort that is close to the best implementation for boubleSort.

Yet as you confirmed in your comment the qSort does better when you have over 10000 items, slowing just how much better qSort scales.