#include iostream.h>
#include stdio.h>
#include conio.h>
void print(int x[], int first)
{
for(int k=0;k < first;k++)
printf("%d ,",x[k]);
cout << endl << endl;
}
int getarray(int x[],int first)
{
int i;
for(i=0;i {
printf("Enter element %d : ",i+1);
scanf("%d",&x[i]);
}
return (x[first]);
}
/////////////Shell sort//////////////////////////////////////
void shell_sort (int *a, int n) {
int h, i, j, k;
for (h = n; h /= 2;) {
for (i = h; i < n; i++) {
k = a[i];
for (j = i; j >= h && k < a[j - h]; j -= h) {
a[j] = a[j - h];
}
a[j] = k;
}
}
}
/////////////Shell sort//////////////////////////////////////
/////////////Merge sort//////////////////////////////////////
void merge(int,int,int,int x[]);
void merge_sort(int low,int high,int x[])
{
int mid;
if(low {
mid=(low+high)/2;
merge_sort(low,mid,x);
merge_sort(mid+1,high,x);
merge(low,mid,high,x);
}
}
void merge(int low,int mid,int high,int x[])
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(x[h]<=x[j])
{
b[i]=x[h];
h++;
}
else
{
b[i]=x[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=x[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=x[k];
i++;
}
}
for(k=low;k<=high;k++) x[k]=b[k];
}
/////////////Merge sort//////////////////////////////////////
/////////////Radix sort//////////////////////////////////////
void radixsort(int a[],int n)
{
int i,b[8],m=0,exp=1;
for(i=0;i {
if(a[i]>m)
m=a[i];
}
while(m/exp>0)
{
int bucket[10]={0};
for(i=0;i bucket[a[i]/exp%10]++;
for(i=1;i<10;i++)
bucket[i]+=bucket[i-1];
for(i=n-1;i>=0;i--)
b[--bucket[a[i]/exp%10]]=a[i];
for(i=0;i a[i]=b[i];
exp*=10;
}
}
/////////////Radix sort//////////////////////////////////////
/////////////Heap sort//////////////////////////////////////
void siftDown(int numbers[], int root, int bottom) {
int maxChild = root * 2 + 1;
// Find the biggest child
if(maxChild < bottom) {
int otherChild = maxChild + 1;
// Reversed for stability
maxChild = (numbers[otherChild] > numbers[maxChild])?otherChild:maxChild;
} else {
// Don't overflow
if(maxChild > bottom) return;
}
// If we have the correct ordering, we are done.
if(numbers[root] >= numbers[maxChild]) return;
// Swap
int temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
// Tail queue recursion. Will be compiled as a loop with correct compiler switches.
siftDown(numbers, maxChild, bottom);
}
void heapSort(int numbers[], int array_size) {
int i, temp;
for (i = (array_size / 2); i >= 0; i--) {
siftDown(numbers, i, array_size - 1);
}
for (i = array_size-1; i >= 1; i--) {
// Swap
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
}
/////////////Heap sort//////////////////////////////////////
/////////////Quick sort//////////////////////////////////////
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
/////////////Quick sort//////////////////////////////////////
/////////////tree sort//////////////////////////////////////
struct tree{
int info;
tree *Left, *Right;
};
tree *root;
class TreeSort{
public:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit();
void insert1(int);
tree *insert2(tree *, tree *);
void display(tree *);
};
void TreeSort::getarray(){
cout<<"How many elements? ";
cin>>no_of_elements;
cout<<"Insert array of element to sort: ";
for(int i=0;i
cin>>elements[i];
}
}
void TreeSort::sortit(){
for(int i = 0; i < no_of_elements; i++){
insert1(elements[i]);
}
}
tree* TreeSort::insert2(tree *temp,tree *newnode){
if(temp==NULL){
temp=newnode;
}
else if(temp->info < newnode->info){
insert2(temp->Right,newnode);
if(temp->Right==NULL)
temp->Right=newnode;
}
else{
insert2(temp->Left,newnode);
if(temp->Left==NULL)
temp->Left=newnode;
}
return temp;
}
void TreeSort::insert1(int n){
tree *temp=root,*newnode;
newnode=new tree;
newnode->Left=NULL;
newnode->Right=NULL;
newnode->info=n;
root=insert2(temp,newnode);
}
/* Inorder traversal */
void TreeSort::display(tree *t = root){
if(root==NULL){
cout<<"Nothing to display";
}else
if(t!=NULL){
display(t->Left);
cout<info<<" ";
display(t->Right);
}
}
/////////////tree sort//////////////////////////////////////
int main(){
int a=1;
while(a>=1){
cout<<"What kind Of sort You Want :"< <<"1- Selection Sort "< <<"2- Bubble Sort "< <<"3- Insertion Sort "< <<"4- Exchange Sort "< <<"5- Quick Sort "< <<"6- Heap Sort "< <<"7- Merge Sort "< <<"8- Tree Sort "< <<"9- Radix Sort "< <<"10- Shell Sort "< <<"0- Exit"<cin>>a;
switch (a)
{
case 1:
{
int* x;
int first,i,j,max,index;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
for(i=first-1;i>=0;i--)
{
max=x[0];
index=0;
for(j=0;j<=i;j++)
if(x[j]>max)
{
max=x[j];
index=j;
}
x[index]=x[i];
x[i]=max;
}
print(x,first);
}
break;
case 2:
{
int* x;
int first,i,temp;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
int flag = 0;
int pass=1;
while(pass<=first&&flag==0)
{
flag=1;
for(i=0;i<=first-pass-1;i++)
if(x[i]>x[i+1])
{
flag=0;
temp=x[i];
x[i]=x[i+1];
x[i+1]=temp;
}
pass=pass+1;
}
print(x,first);
}
break;
case 3:
{
int* x;
int first,i,j,y;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
for(i=1;i<=first-1;i++)
{
y=x[i];
j=i-1;
while(j>=0&&y {
x[j+1]=x[j];
j=j-1;
}
x[j+1]=y;
}
print(x,first);
}
break;
case 4:
{
int* x;
int first,i,j,temp;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
for(i=0;i<=first-1;i++)
for(j=i+1;j if(x[i]>x[j])
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
print(x,first);
}
break;
case 5:
{
int* x;
int first,left=0;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
quickSort(x,left,first);
print(x,first);
}
break;
case 6:
{
int* x;
int first;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
heapSort(x,first);
print(x,first);
}
break;
case 7:
{
int* x;
int first;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
merge_sort(0,first,x);
print(x,first);
}
break;
case 8:
{
TreeSort TS;
TS.getarray();
TS.sortit();
cout< TS.display();
cout< }
break;
case 9:
{
int* x;
int first;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
radixsort(x,first);
print(x,first);
}
break;
case 10:
{
int* x;
int first;
printf("Enter Size of aray : ");
scanf("%d",&first);
x=new int[first];
getarray(x,first);
shell_sort(x,first);
print(x,first);
}
break;
default: break;
}
}
getch();
return 0;
}