Sort Algorithms: Quick Sort, Merge Sort, Radix Sort, Heap Sort and Shell Sort in One Program

Hi GuyZ,
     This is the source code which contains Quick Sort, Merge Sort, Radix Sort, Heap Sort and Shell Sort algorithms implementation.

Source Code

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
class Show{
public:
    void show(int *arr, int n){
        cout<<"Sorted List: ";
        for (int i=0;i<n;i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
};

class merge:public Show{
    int a[1024], sort[1024], n, i, j, tmp, k;


    void divide(int beg, int end){
        if((end-beg)>=1){
            int mid = (beg+end)/2;
            divide(beg, mid);
            divide(mid+1, end);
            arrange(beg, mid, end);
        }
    }
    void arrange(int beg, int mid, int end){
        i=k=beg;
        j=mid+1;
        while(i<=mid && j<=end){
            if(a[i]<a[j]){
                sort[k++]=a[i++];
            }
            else{
                sort[k++]=a[j++];
            }
        }
        while(i<=mid){
            sort[k++]=a[i++];
        }
        while(j<=end){
            sort[k++]=a[j++];
        }
        for(i=beg;i<=end;i++){
            a[i]=sort[i];
        }
    }
public:
    void read(){
        cout<<"Enter limit: ";
        cin>>n;
        cout<<"Enter "<<n<<" items: ";
        for(i=0;i<n;i++){
            cin>>a[i];
        }
        divide(0, n-1);
        show(a, n);
    }
};

class heapsort:public Show{
    int n, arr[1024], tarr[1024];

    int buildTree(int n){
        tarr[1] = arr[0];
        int i = 2;
        while(i<=n){
            tarr[i] = arr[i-1];
            int parent = i/2;
            int base = i;
            while(tarr[parent]<tarr[i] && parent>0){
                int t = tarr[parent];
                tarr[parent] = tarr[i];
                tarr[i] = t;
                parent = parent/2;
                i = parent;
            }
            i = base+1;
        }
        int j = 0;
        for(i=2;i<n+1;i++){
            arr[j++] = tarr[i];
        }
        return tarr[1];
    }
public:
    void read(){
        cout<<"Enter the limit: ";
        cin>>n;
        cout<<"Enter "<<n<<" items: ";
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        int t = n;
        while(t){
            arr[t-1] = buildTree(t); 
            t--;
    }
    show(arr, n);
    }
};

class quick:public Show{
    int a[1024], i, j, tmp, n;

    void quickSort(int *a, int beg, int end){
        if(beg<end){
            int pivot = partition(a, beg, end);
            quickSort(a, beg, pivot-1);
            quickSort(a, pivot+1, end);
        }
    }
    int partition(int *a, int beg, int end){
        int pivot = a[beg];
        int flg = false;
        i = beg+1; j = end;
        while(!flg){
            while(i<=j && a[i]<=pivot){
                i++;
            }
            while(j>=i && a[j]>=pivot){
                j--;
            }
            if(j<i){
                flg = true;
            }
            else {
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        tmp = a[beg];
        a[beg] = a[j];
        a[j] = tmp;
        return j;
    }
public:
    void read(){
        cout<<"Enter limit: ";
        cin>>n;
        cout<<"Enter "<<n<<" items: ";
        for(i=0;i<n;i++){
            cin>>a[i];
        }
        quickSort(a, 0, n-1);
        show(a, n);
    }
};

class shellsort:public Show{
    int n, x, arr[1024];

    void arrange(int *arr, int start, int x, int l){
        int i = start+x;
        while(i<l){
            int val = arr[i];
            int pos = i;
            while(pos>=x && arr[pos-x]>val){
                arr[pos] = arr[pos-x];
                pos = pos-x;
            }
            arr[pos] = val;
            i++;
        }
    }
    void shells(int *arr, int l){
        int start = l/2;
        while(start>0){
            for(int i=0;i<start;i++){
                arrange(arr, i, start, l);
            }
            start=start/2;
        }
    }
public:
    void read(){
        cout<<"Enter limit: ";
        cin>>n;
        cout<<"Enter "<<n<<" items: ";
        for(int i=0;i<n;i++)cin>>arr[i];
        shells(arr, n);
        show(arr, n);
    }
};

class radix:public Show{
    int arr[1024], n, flg, i, nw, d, t;
public:
    void read(){
        cout<<"Enter limit: ";
        cin>>n;
        cout<<"Enter "<<n<<" items: ";
        for(i=0;i<n;i++){
            cin>>arr[i];
        }
        flg = 0;
        d = 1;
        while(!flg){
            flg = 1;
            queue<int> Q[10];
            queue<int> QN[10];
            for(i=0;i<n;i++){
                nw = abs(arr[i]/d);
                if(nw>9){
                    flg = 0;
                }
                if(arr[i]<0)
                    QN[nw%10].push(arr[i]);
                else
                    Q[nw%10].push(arr[i]);
            }
            t = 0;
            for(i=9;i>=0;i--){
                while(!QN[i].empty()){
                    arr[t++] = QN[i].front();
                    QN[i].pop();
                }
            }
            for(i=0;i<10;i++){
                while(!Q[i].empty()){
                    arr[t++] = Q[i].front();
                    Q[i].pop();
                }
            }
            d = d*10;
        }
        show(arr, n);
    }
};
class menu{
    int opt;
    heapsort hs;
    shellsort ss;
    radix r;
    quick q;
    merge m;
public:
    void read(){
        opt = 0;
        cout<<"\n\t\t\tMENU\n1. Heap Sort\n2. Shell Sort\n3. Radix Sort\n4. Quick Sort\n5. Merge Sort\n6. Exit";
        while(opt!=6){
            cout<<"\nOption: ";
            cin>>opt;
            switch(opt){
                case 1:
                    hs.read();
                    break;
                case 2:
                    ss.read();
                    break;
                case 3:
                    r.read();
                    break;
                case 4:
                    q.read();
                    break;
                case 5:
                    m.read();
                    break;
                case 6:
                    break;
                default:
                    cout<<"Option Error: Try again...";
                    break;
            }
        }
    }
};
int main()
{
    menu m;
    m.read();
}