Quick Sort

Algorithm

1.  Divide: Split the array into 2 subarrays such that elements in left subarray are less than pivot and in right subarray are greater than pivot.

2.  Conquer: Recursively sort the 2 subarrays.

3.  Combine: Combine all sorted elements in group to form a list of sorted elements.

Algorithm steps

1.Pick an element called a pivot.I have chosen pivot as 1st element for every array.

2.Partition function partitions the array into 2 subarrays,the array on the left of pivot has values less than pivot and the right subarray has values greater than the pivot. In short,partition function places pivot in its correct position.

3.We apply the above steps recursively for both the subarrays separately.

Let Array = 6 5 3 1 8

Below is how array is divided.

                                  6 5 3 1 8
                                 /   |    \
                              1 5 3  6     8
                              /   \
                             1    5 3
                                  /  \
                                  3   5                    

In Red:  Pivots that were placed in their correct position

Code

Quicksort function:Recursively calls quicksort on left array and right array.

Partition function:Partitions the array into 2 subarrays by placing pivot at the right position.Elements at the left of pivot are less than it and at right are greater than it.It returns the position of pivot.

void quicksort(int arr[],int low,int high)          //low and high are passed from main()
{
    int m;
    if(low<high)
    {
        m=partition(arr,low,high);
        quicksort(arr,low,m-1);
        quicksort(arr,m+1,high);
    }
}

int partition(int arr[],int low,int high)
{
    int pivot=arr[low],i=low,j=high;
    while(i<j)
    {
        while((arr[i]<=pivot)&&(i<=high))
            i++;
        while(arr[j]>pivot)
            j--;
        if(i<j)
            swap(arr,i,j);                   //swaps arr[i] and arr[j]
    }
    swap(arr,low,j);                        //swaps arr[low] and arr[j]
    return j;
}

Code Tracing

Lets trace quicksort code for clear understanding using a call stack.

When a function invokes,its activation record is pushed on the call stack and when it finishes execution,its activation record is popped off from the call stack.Activation record comprises of many things but I am just showing the things that help understand recursion.Below I trace the quicksort and partition functions.