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();
}
