Data Structure: Implementing Quick Sort using C/C++

Algorithm

1. Declare and initialize necessary variables
2. Pick a pivot element.
3. FInd the proper position of the pivot element
4. Divide the total array into two sub arrays so that all elements
 of the left sub array are less than pivot and that of right are greater than pivot.
5. Do the quick sort on the each subarrays

Source Code:

#include<iostream>
using namespace std;
class QuickSort{
    public:
        int no_of_elements;
        int elements[10];
    public:
        void getarray();
        void sortit(int [], int, int);
        void partition(int [],int ,int,int&);
        void display();
};
void QuickSort::getarray(){
    cout<<"How many elements?: ";
    cin>>no_of_elements;
    cout<<"Insert array of element to sort: ";
    for(int i=0;i<no_of_elements;i++){
        cin>>elements[i];
    }
}
void QuickSort::sortit(int x[], int lb, int ub){
    int j;
    if(lb >= ub)
    return;
    display();
    partition(x,lb,ub,j);
    sortit(x,lb,j-1);
    sortit(x,j+1,ub);
}
void QuickSort::partition(int x[],int lb,int ub,int &pj){
    int a, down, temp, up;
    a = x[lb];
    up = ub;
    down = lb;
    while(down < up){
        while(x[down] <= a)
            down++;
        while(x[up]  > a)
            up--;
        if(down < up){
            temp = x[down];
            x[down] = x[up];
            x[up] = temp;
        }
    }
    x[lb] = x[up];
    x[up] = a;
    pj = up;
}
void QuickSort::display(){
    for(int i = 0 ; i < no_of_elements; i++){
        cout<<elements[i]<<" ";
    }
    cout<<endl;
}
int main(){
    QuickSort QS;
    QS.getarray();
    cout<<"Sorting is given in step by step showing each iteration"<<endl;
    QS.sortit(QS.elements,0,QS.no_of_elements-1);
    QS.display();
    return 0;
}

Output:



Efficiency of Quick Sort

Assume that file size n is a power of 2 i.e. n = 2^m or m = logn. Also assume proper position of pivot is always at middle. In first pass, there are n comparisons and file splits into subfiles of size n/2 and so on . So total number of comparisons is O(n*m) or O(nlogn).