Sorting collection of Integers using Quick Sort Algorithm

Here is the code:

class Program
    {
        //   This Solution is written by me and is not completely tested. Please comment if you found any alternative solutions or any enhancement to my solution.
        static void Main(string[] args)
        {
            int[] a1 = new int[] { 5, 3, 5, 2, 1, 0, 8, 10, 9, 20, 32 };

            Console.WriteLine("Before Sorting");
            foreach (var item in a1)
            {
                Console.Write(item + ",");
            }

            Quick_Sort(a1, 0, a1.Length - 1);
            Console.WriteLine();
            Console.WriteLine("After Sorting");
            foreach (var item in a1)
            {
                Console.Write(item + ",");
            }
        }
        private static void Quick_Sort(int[] arr, int left, int right)
        {
            int i = left + 1;
            int j = right;
            int pivot = arr[left];
            while (i <= j)
            {
                while (arr[i] < pivot)
                {
                    //Incrementing i till we found a element greater than pivot
                    i++;

                }
                while (arr[j] >= pivot)
                {
                    //For stoping the loop when j==left as decrementing j more will result index out of bound
                    if (j == left)
                    {
                        break;
                    }

                    //Decrementing j till we found a element less than pivot
                    j--;
                }

                if (i < j)
                {


                    //Swaping only when i<j
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }

            }

            //It comes out of loop when j>i So it is Swaping when j>i
            int temp1 = arr[j];
            arr[j] = arr[left];
            arr[left] = temp1;

            //Performing same with a left half array from pivot
            if (left < (j - 1))
            {
                Quick_Sort(arr, left, j - 1);

            }

            //Performing same with a Right half array from pivot
            if ((j + 1) < right)
            {
                Quick_Sort(arr, j + 1, right);
            }

        }



    }

Output:

Before Sorting
5,3,5,2,1,0,8,10,9,20,32,
After Sorting
0,1,2,3,5,5,8,9,10,20,32,Press any key to continue . . .

No comments:

Post a Comment

Popular Posts