sonnd92
5/4/2017 - 2:01 PM

Quick sort algorithm

Quick sort algorithm

//Quick Sort
using System;
class Solution
{
    static void Main(String[] args)
    {
        //Initializing array
        int[] arr = {9, 4, 8, 3, 1, 2, 5};
        Console.Write("Initial Array : ");
        Console.WriteLine(String.Join(" ", arr));
        quickSort(arr, 0, arr.Length - 1);
    }
    //Sorting in non decreasing order
    private static void quickSort(int[] arr, int i, int j)
    {
        if(i < j)
        {
            int pos = partition(arr, i, j);
            quickSort(arr, i, pos - 1);
            quickSort(arr, pos + 1, j);
        }
    }

    private static int partition(int[] arr, int i, int j)
    {
        int pivot = arr[j];
        int small = i - 1;

        for(int k = i; k < j; k++)
        {
            if(arr[k] <= pivot)
            {
                small++;
                swap(arr, k, small);
            }
        }

        swap(arr, j, small + 1);
        Console.WriteLine("Pivot = " + arr[small + 1]);
        Console.WriteLine(String.Join(" ", arr));
        return small + 1;
    }

    private static void swap(int[] arr, int k, int small)
    {
        int temp;
        temp = arr[k];
        arr[k] = arr[small];
        arr[small] = temp;
    }


}