Quick Sort in Cpp

/*
 *  This takes a pointer and makes changes directly in the array, so it is an
* in-place algorithm and quickSort func uses another func, partition to
 * get the index of the pivot in each recursion
*
*/
#include <iostream>
using namespace std;
int partition(int* arr,int l,int r){
    int pivot=arr[r];
    int i=l-1;
    int temp;
    for(int j=l;j<r;j++){
        if(arr[j]<=pivot){
            i+=1;
            temp=arr[j];
            arr[j]=arr[i];
            arr[i]=temp;
        }
    }
    temp=arr[i+1];
    arr[i+1]=arr[r];
    arr[r]=temp;
    return i+1;
}
void quickSort(int* arr,int l,int r){
    if(l<r){
        int pi=partition(arr,l,r);
        quickSort(arr,l,pi-1);
        quickSort(arr,pi+1,r);
    }
}

int main() {
    cout<<"Hola Todo El Mundo!\n";
    return 0;

} 

Comments

Popular Posts