Rumyhub

The place where stuff Happens

Quick Sort Algorithm

Quicksort Explanation

Quicksort is sorting alogrithm which is a divide and conquer sorting algorithms which means that is done by splitting the array by the pivot ideally being in the middle and rearrange so that the right side value are greater than the pivot and the left is less than the pivot. 

This is done recursively tghrough the array until only two values are reached and then similar to the Merge sort the array is then automatically sorted.

The following video explaines the algorithm using a hungarian folk dance. 


The video shows how the quick sort method easily works by using a very creative way to explain.

How to using C#

As explained above the quick sort algorithm sorts an array of randoms, and for the example I have used the Generation algorthim found in my security layer (but the default random of the .NET framework will do) and generated and array of 1,000,000 with random integers from 0 to 10,000 as shown below.

 int[] array = new int[1000000];
 for (int i = 0; i < array.Length; i++) {
array[i] = RandomGenerater.RandomType(0, 10000);
}
And wrote the array to file using the following code, this code is used to later compare the data side by side instead of storing the values in the ram.

private static void WriteToFile(string value, string filename)
{
using (System.IO.StreamWriter file = new System.IO.StreamWriter(System.Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments) + @"/"+filename+".txt", true))
{
    file.WriteLine(value);
    }
}

The quicksort which is explained is modified to automatically choose a median from the array. A method chooses 3 random elements from the array and chooses the median between the 3. Please note that the array is copied by value, not by reference. This is not to intefere with the main array when retrieving the pivot.

private static int MedianElement(int[] arr, int elementNo)
{
int[] _tmp = arr;
    if (arr.Length > elementNo)
    {
    _tmp = new int[elementNo];
        Random r = new Random();
        for (int i = 0; i < elementNo; i++)
        {
        _tmp[i] = arr[r.Next(0, arr.Length - 1)];
        }
    }
    Array.Sort(_tmp);
    float median = _tmp.ElementAt(elementNo / 2) + _tmp.ElementAt((elementNo - 1) / 2);
    median /= 2;
    return (int)median; }

Now for the quick sort, to better understand the method, I will build part by part. First step is to set boundaries to the current array.

int left = low;
int right = high;

Next step is to get the pivot by using the above method. (This part can be omitted by getting the left most item in the array).

int[] _arr = new int[(high - low) + 1];
Array.Copy(arr, low, _arr, 0, (high - low) + 1);
int pivot = MedianElement(_arr, elementNo);

Third Step is to loop tghrough the parts of the array adjacent to the array by simply using a never-ending while loop which will be break when the pivot is sorted.

Now to start the sorting inside the never-ending loop, I have started by checking the right side of the pivot, and if the value is greater the pivot it will enter the while loop and reduce the right value set above by one. This way the greater  value is remained on the right side. 

while (arr[right] > pivot)
{
right--; }

As shown above only if the value is greater than the pivot will enter the loop. If the while loop has found a value smaller or has reach the end of the array the loop will be stoped and the next checking will start, instead this time it will switch to left side. To keep values smaller than the pivot on the left therefore ensuring that the pivot will always have greater values on the right and smaller values on the left.

while (arr[left] < pivot)
{
  left++; }

Now incase that 2 values are the same the quick sort should skip them and leave both values the same place as they are already sorted.

if (arr[left] <= arr[right] && right != low)
{
   right--;
}

As you may not that statement contains an extra element which checks whether the right counter has reached the first element in the array which in that case skips it.

Now for the second part of the if statement the else if, The part check whether the left counter is less than the right counter which means that swap is needed between the array item at the left counter , with the array item at the right counter.

else if (left < right)
{
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

Now if the quicksort arrives at the next step in the main loop that means the pivot has been sorted in place and the main while loop can be stoped or breaked;

else
{
    break;
}

And here is the whole code inside the quick sort.

while (true)
{
    while (arr[right] > pivot)
    {
       right--;
    }
    while (arr[left] < pivot)
    {
       left++;
    }
    if (arr[left] <= arr[right] && right != low)
    {
       right--;
    }
    else if (left < right)
    {
       int temp = arr[left];
       arr[left] = arr[right];
       arr[right] = temp;
    }
    else
    {
       break;
    }
}

Now that we have sorted the pivot is time to sort the adjacent arrays. First I checked whether the first element index is the same as the last element index. This is to stop from further spliting the array up when reaching a single element.

The next line recursively call the same method but supplies the information to sort the first part and the second line recursively call the same method but supplies the information to sort the second part of the array. This is done until all the array has been sorted.

if (low < high)
{
   QuickSort_Median(arr, low, right, elementNo);
   QuickSort_Median(arr, left + 1, high, elementNo);
}

This step can also be done using threads but bare in mind that this method will require a very complex thread mangement becuase of the sheer amount of threads that on can have which may or may not slow the process instead of speeding it up.

The last part added to the algorithm is just a sanity check to check whether the low is greater or equal to high value the method will stop and return.

if (low >= high)
{
     return;
}

And here is the whole code

        private static void QuickSort_Median(int[] arr, int low, int high, int elementNo = 3)
        {
            if (low >= high)
            {
                return;
            }

            int left = low;
            int right = high;

            int[] _arr = new int[(high - low) + 1];
            Array.Copy(arr, low, _arr, 0, (high - low) + 1);

            int pivot = MedianElement(_arr, elementNo);

            while (true)
            {
                while (arr[right] > pivot)
                {
                    right--;
                }
                while (arr[left] < pivot)
                {
                    left++;
                }
                if (arr[left] <= arr[right] && right != low)
                {
                    right--;
                }
                else if (left < right)
                {
                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
                else
                {
                    break;
                }
            }

            if (low < high)
            {
                QuickSort_Median(arr, low, right, elementNo);
                QuickSort_Median(arr, left + 1, high, elementNo);
            }
        }

Benefits of this Quick Sort over the default Quick Sort

  • The pivot is choses randomly and possibly the center of the array instead of starting from the left most which is not always the greates option especially when the array is almost sorted.
  • Does not need extra space to store the elements during checking and swapping becuase it is always using the same array, this is very important when space might be a problem.
  • Fast with an average of 1.7 seconds to sort a array of 1 Million random intergers from 0 to 10000.

Download Link: QuickSort.zip (51.9KB)

blog comments powered by Disqus