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

Algorithm

Loading...
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:

 

QuickSort

 

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).

Loading...
SHARE Data Structure: Implementing Quick Sort using C/C++

You may also like...

2 Responses

  1. Anonymous says:

    Your codes are actually a lifesaver man….
    thanks a lot..

    Would you please give me the most optimized code for Heap Sort through C++
    give me the Link…. I didn't find it on your website..

Leave a Reply

Your email address will not be published. Required fields are marked *

Share