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
 
 
 
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(){
 
    coutHow many elements?: ";
 
    cin>>no_of_elements;
 
    coutInsert array of element to sort: ";
 
    for(int i=0;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 
 
        while(x[down] 
 
            down++;
 
        while(x[up]  > a)
 
            up--;
 
        if(down 
 
            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 
 
        cout ";
 
    }
 
    cout
 
}
 
 
 
int main(){
 
    QuickSort QS;
 
    QS.getarray();
 
    coutSorting is given in step by step showing each iteration"
 
    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).