C # QuickSort too slow

Question

Now I am studying different types of sorting, and I found out that starting from a certain point, my QuickSort algorithm does not work so fast.

Here is my code:

class QuickSort
    {

       // partitioning array on the key so that the left part is <=key, right part > key
            private int Partition(int[] arr, int start, int end)
            {
                    int key = arr[end];
                    int i = start - 1;
                    for (int j = start; j < end; j++)
                    {
                            if (arr[j] <= key) Swap(ref arr[++i], ref arr[j]);
                    }
                    Swap(ref arr[++i], ref arr[end]);
                    return i;
            }


            // sorting
            public void QuickSorting(int[] arr, int start, int end)
            {
                    if (start < end)
                    {
                            int key = Partition(arr, start, end);
                            QuickSorting(arr, start, key - 1);
                            QuickSorting(arr, key + 1, end);
                    }
            }
      }


    class Test
    {
            static void Main(string[] args)
            {                       
                    QuickSort quick = new QuickSort();
                    Random rnd = new Random(DateTime.Now.Millisecond);

                    int[] array = new int[1000000];

                    for (int i = 0; i < 1000000; i++)
                    {
                            int i_rnd = rnd.Next(1, 1000);
                            array[i] = i_rnd;
                    }

                    quick.QuickSorting(array, 0, array.Length - 1);

            }
      }

It takes about 15 seconds to run this code in an array of a million elements. Although, for example, MergeSort or HeapSort do the same in less than a second.

Could you explain to me why this could happen?

Answer 1

How fast your sorting is and what algorithm you should use depends on a lot of your input. This is random, almost sorted, reverse, etc.

There is a very nice page that illustrates the operation of various sorting algorithms:

• Animating Sort Algorithms

Answer 2

, Swap? , , JIT .

quicksort Edulinq - (, ), , . , , .

- , .

Answer 3

1,000,000 1000 . , , 1000 . O (n ^ 2).

1000 , , log2 (1000), 10. (, . ) 10 000 000 .

1000 , 1000 . 1000 1000 + 999 + 998 +... + 1 . ( quicksort , /.) 500 000 000 . 1000 - 1000 1000 * 10 = 10 000 000. - , quicksort . , , .

, , O(N^2) O(N logN). O(N^2).

---

To improve your code: go to 3 parts. Smaller than the hinge, equal to the axis of rotation and larger than the support rod. Then, only quicksort the first and last sections. You will need to make an additional comparison; check equality first. But I think that for this input it would be much faster.