Quicksort using C#

This article will look at how quicksort works and the code in C#.

Today you can sort an array without knowing what is behind the scene. For example, you can sort an array like the below.

String[] words = { “The”, “QUICK”, “BROWN”, “FOX”, “jumps”,

                         “over”, “the”, “lazy”, “dog” };

Array.Sort(words);

You never know what is going on at the back.

The sort could be using one of the sorting algorithm. Let’s look at quicksort.

Looking at the code I get it from http://www.softwareandfinance.com/CSharp/QuickSort_Iterative.html.

namespace CSharpSort

{   

    class Program

    {

        static public int Partition(int[] numbers, int left, int right)

        {

            int pivot = numbers[left];

 

            while (true)

            {

                while (numbers[left] < pivot)

                    left++;

 

                while (numbers[right] > pivot)

                    right–;

               

                if (left < right)

                {

                    int temp = numbers[right];

 

                    numbers[right] = numbers[left];

 

                    numbers[left] = temp;

                }

                else

                {

                    return right;

                }

            }

        }

 

        struct QuickPosInfo

        {

 

            public int left;

 

            public int right;

 

        };

 

        static public void QuickSort_Iterative(int[] numbers, int left, int right)

        {

 

            if (left >= right)

                return; // Invalid index range

 

            List<QuickPosInfo> list = new List<QuickPosInfo>();

 

            QuickPosInfo info;

            info.left = left;

            info.right = right;

 

            list.Insert(list.Count, info);

 

            while (true)

            {

                if (list.Count == 0)

                    break;

 

                left = list[0].left;

                right = list[0].right;

                list.RemoveAt(0);

 

                int pivot = Partition(numbers, left, right);

 

                if (pivot > 1)

                {

                    info.left = left;

                    info.right = pivot – 1;

                    list.Insert(list.Count, info);

                }

 

                if (pivot + 1 < right)

                {

                    info.left = pivot + 1;

                    info.right = right;

                    list.Insert(list.Count, info);

                }

            }

        }

 

        static void Main(string[] args)

        {

 

            int[] numbers = { 3, 8, 7, 5, 2, 1, 9, 6, 4 };

 

            int len = 9;

 

            Console.WriteLine(“QuickSort By Iterative Method”);

 

            QuickSort_Iterative(numbers, 0, len – 1);

 

            for (int i = 0; i < 9; i++)

                Console.WriteLine(numbers[i]);

        }

    }

}

You can see the code download partition to get the pivot then swap them.

Below is the animation to example Quicksort.

http://www.csanimated.com/animation.php?t=Quicksort

There is also a video in youtube for QuickSort.

https://www.youtube.com/watch?v=8hHWpuAPBHo

You can also download a single solution from http://skydrive.live.com. The sample file name is ConAppSort.zip My MSN ID is chanmmn@hotmail.com.

About chanmingman

Since March 2011 Microsoft Live Spaces migrated to Wordpress (http://www.pcworld.com/article/206455/Microsoft_Live_Spaces_Moves_to_WordPress_An_FAQ.html) till now, I have is over 1 million viewers. This blog is about more than 50% telling you how to resolve error messages, especial for Microsoft products. The blog also has a lot of guidance teaching you how to get stated certain Microsoft technologies. The blog also uses as a help to keep my memory. The blog is never meant to give people consulting services or silver bullet solutions. It is a contribution to the community. Thanks for your support over the years. Ming Man is Microsoft MVP since year 2006. He is a software development manager for a multinational company. With 25 years of experience in the IT field, he has developed system using Clipper, COBOL, VB5, VB6, VB.NET, Java and C #. He has been using Visual Studio (.NET) since the Beta back in year 2000. He and the team have developed many projects using .NET platform such as SCM, and HR based applications. He is familiar with the N-Tier design of business application and is also an expert with database experience in MS SQL, Oracle and AS 400.
This entry was posted in .Net and tagged , . Bookmark the permalink.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s