Friday, December 2, 2011

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:


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

2 comments:

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

    ReplyDelete