Quicksort, C# - rextester

Quicksort

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            /*
            Quicksort is a divide and conquer algorithm. Here Quicksort first divides a large array into two smaller sub-array: 
            the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.
            
            Quick Sort is a sorting algorithm that uses the divide and conquer method. It takes a pivot element and places it in its correct position. 
            Then the array to the left and right of the pivot element are again sorted using Quick Sort. This is done until the whole array is sorted.
            
            Divide: Rearrange the elements and split the array into two subarrays and an element in between such that so that 
            each element in the left subarray is less than or equal the middle element and each element in the right subarray is greater than the middle element.

Conquer: Recursively sort the two subarrays.
                        
            */
            int [] nums = { 12, 19, 15, 8, 4, 6, 3, 29, 9, 2, 22, 44, 20, 25 };
            int n = nums.Length;
            QuickSort quick = new QuickSort(); 
            
            Console.WriteLine("Before hsort, the array is"); 
            quick.Display(nums);
            
            quick.Sort(nums, 0, n-1); 
            Console.WriteLine("Sorted array is"); 
            quick.Display(nums); 
        }
    }
    
    public class QuickSort {
          public int Partition(int[] arr, int left, int right) {
             int pivot;
             pivot = arr[left];
             while (true) {

while (arr[left] < pivot) {
                   left++;
                }

while (arr[right] > pivot) {
                   right--;
                }

if (left < right) {
                   int temp = arr[right];
                   arr[right] = arr[left];
                   arr[left] = temp;
                } else {
                   return right;
                }
             }
          }

public void Sort(int[] arr, int left, int right) {
             int pivot;
             if (left < right) {
                pivot = Partition(arr, left, right);
                if (pivot > 1) {
                   Sort(arr, left, pivot - 1);
                }
                if (pivot + 1 < right) {
                   Sort(arr, pivot + 1, right);
                }
             }
          }

// Display the array 
         public  void Display(int []arr) { 
                int size = arr.Length; 
                for (int indx=0; indx < size; ++indx) 
                    Console.Write(arr[indx] + " "); 
                Console.WriteLine(); 
         }
    }
    
}


run \| edit \| history \| help	0