Tuesday, April 20, 2010

Recalling quick sort while downloading Visual Studio Service Pack



using System;
using System;
using System.Collections.Generic;
using System.Text;

namespace TestQuicksort
{
    class Program
    {

        
        static void Main(string[] args)
        {
            int[] r = new int[] { 6, 4, 5, 1, 8, 9, 3, 7, 2, 0 };


            Action print = () =>
            { for (int i = 0; i < r.Length; ++i) 
                  Console.Write("{0,4}", r[i]); }; 

            print();

            Qsort(r, 0, r.Length - 1);

            Console.WriteLine("\n");

            print();

            Console.ReadLine();
            
        }

        private static void Qsort(int[] r, int a, int z)
        {
            int i = a;
            int j = z;

            int segregator = r[new Random().Next(a,z)];            

            while (i < j)
            {
                while (r[j] > segregator) --j;
                while (r[i] < segregator) ++i;

                if (i <= j)
                {
                    if (i < j)
                    {
                        int x = r[i];
                        r[i] = r[j];
                        r[j] = x;
                    }

                    --j;
                    ++i;
                }

            }

            if (j > a)
                Qsort(r, a, j);

            if (i < z)
                Qsort(r, i, z);


        }
    }//class Program
}

No comments:

Post a Comment