Algorithms, C#

Let us QuickSort in C#

I must agree that QuickSort was one of the first Algorithms I staggered and stumbled upon.

It still mesmerizes me on how Mr. Hoare came up with clever, yet so simple way to sort elements.

It has been a while I have written a sorting algorithm, mostly because of the fact I happen to code in C# and sorting and searching is one among various algorithms we take for granted.

So I tried to code it in C# and here it goes:

 

public static class QuickSorter
   {
       public static void QuickSort(int[] array, int left, int right)
       {
           if (left < right)
           {
               int q = Partition(array, left, right);
               QuickSort(array, left, q - 1);
               QuickSort(array, q + 1, right);
           }
       }
 
       private static int Partition(int[] array, int left, int right)
       {
           int pivot = array[right];
           int i = left-1;
 
           for (int j = left; j < right; j++)
           {
               if (array[j] <= pivot)
               {
                   i++;
                   int temp = array[i];
                   array[i] = array[j];
                   array[j] = temp;
               }
 
           }
 
           int temp1 = array[right];
           array[right] = array[i+1];
           array[i+1] = temp1;
 
           return i + 1;
       }
   }

Final words

Sorting algorithms come in various flavors and each one has a reason and use case to exist.

In fact the Array.Sort method that we often use in C# internally uses Insertion sort/Quick Sort/ Heap sort depending on the input and in case you were to do a stable sort, Array.Sort may not be the right fit for you.

Whenever in doubt I always refer the Sorting Algorithm comparison chart on Wikipedia.

I will follow up with more sorting algorithms and will see when and why to use it.

Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s