Program For Quick Sort in C++

Program For Quick Sort in C++

Quick Sort is an example of divide-and-conquer algorithmic technique. 

It is also called partition exchange sort. It uses recursive calls for for sorting the elements. 

It is One of famous algorithms among comparison-based sorting Algorithms.

Algorithm :-

The Recursive algorithm consists of Four Steps :

1. if there are one or no elements in the array to be sorted, return
2. Pick up an element in the array to serve as ''pivot"  point. (usually  the left-most element in the array is used.)
3. Split the array into two-parts -one with elements larger than the pivot and the other with elements smaller than the pivot.
4. Recursively repeat the algorithm for the both halves of the original array.

#include <iostream>
using namespace std;

void quickSort( int * arr, int left, int right ) {
    
    if( left >= right ) {
        return;
    }
    
    int leftHold = left, rightHold = right;
    
    int pivot = arr[left];
    
    while( left < right ) {
   
        while( arr[right] > pivot && left != right ) {
            right--;
        }
    
        if( left != right ) {
            arr[left] = arr[right];
            left++;
        }
    
        while( arr[left] < pivot && left != right ) {
            left++;
        }
    
        if( left != right ) {
            arr[right] = arr[left];
            right--;
        }
    }
    
    

 arr[left] = pivot;
    
    quickSort(arr, leftHold, left-1 );
    quickSort(arr, left+1, rightHold );
    
}

int main(int argc, const char * argv[]) {
   
    int arr[] = { 55, 25, 16, 98, 3, 43, 23, 19, 66, 82 };
    quickSort(arr, 0, 9 );
    
    for( int i = 0; i < 10; i++ ) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    
    return 0;
}