0
\$\begingroup\$

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?

\$\endgroup\$

closed as off-topic by RubberDuck, SuperBiasedMan, Vogel612, Ethan Bierlein, Mathieu Guindon Jan 21 '16 at 15:11

If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ If I were you, I'd write many test cases, with different kind of arrays (sorted, reversed, shuffled, all values different, a single value, etc) of different size (empty, small, huge) and ensure that data are properly sorted. Once you've done this, it will be easier to spot if something is wrong in either the correctness or the performances and understand why things do not work the way is it expected. \$\endgroup\$ – Josay Mar 24 '14 at 13:23
  • 2
    \$\begingroup\$ Also: don't run a performance test only once – you are still in the millisecond range. Instead: Try counting the number of iterations during a three-second run for a better benchmark. Notice also that your bubblesort works in-place, whereas the quicksort copies each item multiple times. \$\endgroup\$ – amon Mar 24 '14 at 13:37
  • \$\begingroup\$ The code to set pivot to a reasonble value seem to be missing. \$\endgroup\$ – Ian Ringrose Mar 24 '14 at 15:10
  • 5
    \$\begingroup\$ I'm voting to close this question as off-topic because Questions asking for explanations of code behavior is off topic. \$\endgroup\$ – RubberDuck Jan 21 '16 at 12:17
  • \$\begingroup\$ please read this article : quora.com/Which-is-faster-quicksort-or-bubble-sort \$\endgroup\$ – chillworld Jan 21 '16 at 12:53
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You were right, the scaling became significant after an array size of ca. 10000 though. \$\endgroup\$ – チーズパン Mar 24 '14 at 14:56
  • 1
    \$\begingroup\$ @bodycountPP, Also your qSort could be written to be a lot faster by not creating 3 new arrays, it is also very important to quickly choose a good item to privet on. \$\endgroup\$ – Ian Ringrose Mar 24 '14 at 15:12

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