Wednesday, 4 September 2013

Generic Quick Sorting - C#

In this article we are going to see the Generic Quick Sorting implementation using C#.

Quick Sort :




Quick Sort is a Divide and conquer algorithm, It divides the collection int to two sub sets based on the pivot element selected, one subset is a collection elements which is smaller than pivot, another subset is collection of elements consists of larger than pivot.then each subsets are undergoes following steps again.Entire sort can be done in O(log n)

Steps :
1. Consider a element as Pivot from the List.
2. ReOrder the list so the elements which are lesser than pivot arrange previous in the order of the pivot and     the elements which are higher than pivot arrange next in the order of the pivot.
3. Recursively apply the above steps to each two subsets individually.


Algorithm :

function quicksort('array')
      if length('array')1
          return 'array' 
      for each 'x' in 'array'
          if 'x''pivot' then append 'x' to 'less'
          else append 'x' to 'greater'

      return concatenate(quicksort('less'), list('pivot'), quicksort('greater'))


Now Let we see this implementation in C#

        First Derive a Generic List<T> which is comparable, Then add collection to it ,Add a additional method to it as Order to order a collection based on the Quick Sort by implementing the algorithm. Following type in Generic so any data type can be sorted using this.


class Quicksort<T>:List<T> where T : IComparable
    {
        public List<T> Order()
        {           
            return SortList(this.ToList<T>());
        }

        public  List<T> SortList(List<T> values)
        {
            List<T> _left = new List<T>();
            List<T> _right = new List<T>();

            if (values.Count() > 1)
            {
                T pivot = values[values.Count - 1];
                values.RemoveAt(values.Count - 1);

                foreach (T each in values)
                {
                    if (each.CompareTo(pivot) == 1)
                    {
                        _right.Add(each);
                    }
                    else
                    {
                        _left.Add(each);
                    }
                }
                return MergeList(SortList(_left), pivot, SortList(_right));
            }
            return values;
        }

        private List<T> MergeList(List<T> left, T pivot, List<T> right)
        {
            left.Add(pivot);
            left.AddRange(right);
            return left;
        }

    }


 Now create a Two list one with int type other with string type and order the collection using Quick sort.

class Program
    {
        static void Main(string[] args)
        {
            Quicksort<int> _sorting = new Quicksort<int>();
            _sorting.AddRange(new int[] { 3,1,8,45,2,5,7});
            Console.WriteLine("Ordering the numbers using Quick Sort");
            foreach (int s in _sorting.Order())
            {
                Console.WriteLine(s);
            }

            Quicksort<string> _names = new Quicksort<string>();
            _names.AddRange(new string[]{"Rajesh","Suresh","Pavi","Anna","Ganesh","Sathish","Kani","Hanish","Babu","Dilli"});
            Console.WriteLine();
            Console.WriteLine("Ordering the names using Quick Sort");
            foreach (string s in _names.Order())
            {
                Console.WriteLine(s);
            }
            Console.Read();
        }
    }



Output :




From this article you can learn the Generic Quick Sorting algorithm in C# and the process of algorithm.

3 comments:



  1. It is really a great work and the way in which u r sharing the knowledge is excellent.
    Thanks for helping me to understand basic concepts. As a beginner in Dot Net programming your post help me a lot.Thanks for your informative article. Dot Net Training in chennai | Dot Net Training in velachery

    ReplyDelete
  2. Given so much information in it. its very useful .perfect explanation about Dot net framework.Thanks for your valuable information. dot net training in chennai velachery | dot net training institute in velachery

    ReplyDelete
  3. This is an amazing blog,it gives very helpful messages to us.Besides that Wisen has established as Best Dot Net Training in Chennai. or learn thru ASP.NET Online Training . Nowadays Dot Net has tons of job opportunities on various vertical industry.

    ReplyDelete