Handwritten quick sort QuickSort excerpt

Recently, I am writing a function that needs to calculate the median, and then I need to call the sorting function of the array. So the author's own sorting function is very curious. After checking, it is found that the self-contained sorting is actually the application's quick sorting. In order to better understand the quick sorting and understand its more appropriate use scenarios, it is manually implemented and recorded:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static int[] test = new int[] {6,1,4,3,5,8 };
        /// <summary>
        ///One quick sort
        /// </summary>
        ///< param name = "a" > array to be arranged < / param >
        ///< param name = "low" > sorting start value < / param >
        ///< param name = "high" > sorting highest value < / param >
        ///<returns> central value position </returns>
        public static int Partition(ref int[] a,int low,int high) {
            // Set central value
            int pivotkey = a[low];
            // Make sure not to enter the dead cycle. Stop when the low pointer is greater than high
            while (low < high) {
                // If the value of the high Sentry is less than the central value, then the high value is exchanged with the central value (the central value saves the copy pivot key!)
                while (low < high && a[high] >= pivotkey)
                    high--;
                a[low] += a[high];
                a[high] = a[low] - a[high];
                a[low] -= a[high];
                // If the low Sentinel's value is greater than the central value, exchange the low with the central value
                while (low < high && a[low] <= pivotkey)
                    low++;
                a[low] += a[high];
                a[high] = a[low] - a[high];
                a[low] -= a[high];
            }
            // At the end of the comparison, low and high will collide. At this time, insert the central value copy value into the low position
            a[low] = pivotkey;
            return low;
        }

        /// <summary>
        ///Quick sort 
        /// </summary>
        ///< param name = "a" > array to be arranged < / param >
        ///< param name = "low" > sorting start value < / param >
        ///< param name = "high" > sorting highest value < / param >
        public static void QuickSort(ref int[] a, int low, int high) {
            // Add this low < high, one is to ensure that the length of the array is greater than 1, the other is to determine the conditions for the end of the recursion, so as to prevent entering the dead loop and stack overflow
            if (low < high) {
                // Location of central value obtained each time
                int pivotloc = Partition(ref a, low, high);
                // The ordered array is divided into two parts by using the central value, and then sorted from low to pivotkey-1 and pivotkey+1 to high
                // Compare the length of both ends to reduce the maximum stack depth (to log n)
                if ((pivotloc - low) <= (high - pivotloc))
                {
                    QuickSort(ref a, low, pivotloc - 1);
                    QuickSort(ref a, pivotloc + 1, high);
                }
                else {                   
                    QuickSort(ref a, pivotloc + 1, high);
                    QuickSort(ref a, low, pivotloc - 1);
                }

                

            }
        }

        static void Main(string[] args)
        {
            QuickSort(ref test,0,test.Length-1);
            foreach (var item in test)
            {
                Console.Write(item + " ");
            }
            Console.ReadKey();
        }
    }
}



Data shows that fast sorting is currently considered the best internal sorting algorithm in terms of average time!

Tags: less

Posted on Sun, 05 Apr 2020 17:27:38 -0700 by flipis