Posts tagged ‘sift’

February 1, 2011

Classic basic sorting and other algorythms. C++ Programming code


/*
void enter(int &m;int b);
void print(int m ;int b[]);
void copy_array(int m;int s[]);
void insertion_sort(int m;b[]);
*/
#include<iostream.h>
void enter(int m,int *b)
{

for(int i=0;i<m;i++)
{
cout<<“input element number:  “<<i+1<<”   “;
cin>>*(b+i);
cout<<“n”;
}
}
void print(int m ,int *b)
{
for (int i=0;i<m;i++)
{
cout<<“element number  “<<i+1<<”   “<<*(b+i)<<“n”;
}
}
void print2(int m ,int b[])
{
for (int i=0;i<m;i++)
{
cout<<“element number  “<<i+1<<”   “<<b[i]<<“n”;
}
}
void copy(int m,int *b,int *s)
{
for (int i=0;i<m;i++)
*(s+i)=*(b+i);
}
void direct_sort(int m,int *b)
{
int k;
for (int i=0;i<m;i++)
for (int j=i+1;j<m;j++)
{
if(*(b+i)<*(b+j))
{
k=*(b+i);
*(b+i)=*(b+j);
*(b+j)=k;
}
}

}
//////
void iron_sort(int m, int *b)
{
int k=0;
for (int i=m-1;i>0;i–)
{
for (int j=0;j<i;j++)
{
if (*(b+j) > *(b+j+1))
{
k=*(b+j);
*(b+j)=*(b+j+1);
*(b+j+1)=k;
}
}
}
}
void bubble_sort(int m,int *b)
{
int k;
for(int i=0;i<m-1;i++)
{
for (int j=m-2;j>=i;j–)
{
if (*(b+j) > *(b+j+1))
{
k=*(b+j);
*(b+j)=*(b+j+1);
*(b+j+1)=k;
}
}
}
}
int sort_matrix(int m,int *b,int x)
{

//int r=m,l=0;
//int M=(m+2)/2;
for(int i=0;i<m;i++)
{

//if(x<*(b+i))        r=M-1;
//if (x>*(b+i))        l=M+1;
if (x==*(b+i)){    return i;}
}
cout<<“no such element in the matrix”;
return m;
}
void merge(int m,int n,int *b,int *c,int *d)
{
int j=0,i=0,k=0;
while(k<m+n)
{

if(*(b+i)>*(c+j))
{edno:if(j<n){*(d+k)=*(c+j); j++;k++;} else goto dve;}
else
{dve:if(i<m){*(d+k)=*(b+i);i++;k++;} else goto edno;}
}
}
void merge2(int m,int n,int *b,int *c,int *d)
{
int i=0,j=0,k=-1;
while(i<m&&j<n)
{
k++;
if (*(b+i)<=*(c+j))
{
*(d+k)=*(b+i);
i++;
}
else
{
*(d+k)=*(c+j);
j++;
}
}
if(i>m-1)
for(int t=j;t<n;t++)
{    k++;
*(d+k)=*(c+j);
}
if(j>n-1)
for(int t=i;t<m;t++)
{    k++;
*(d+k)=*(b+i);
}

}
int fibonacci(int n)
{
if(n==0) return 0;
if(n==1) return 1;
int i=0,*a;
a=new int[n+1];
*(a+0)=0;
*(a+1)=1;
for(int j=1;j<n;j++)
{
*(a+j+1)=*(a+j-1)+*(a+j);
}
unsigned long int s=*(a+n);
return s;
}
void QuickSort(int l,int r,int *a)
{
int i,j,x,y;
i=l;j=r;
if((l+r)%2==0) x=*(a+((l+r)/2));
else x=*(a+(l+r+1)/2);
do
{
while(*(a+i)<x)
i++;
while(*(a+j)>x)
j++;
if(i<=j)
{ y=*(a+i);*(a+i)=*(a+j);*(a+j)=y;i++;j–;};
}while(i<=j);
if (l<j) QuickSort(l,j,a);
if(i<r) QuickSort(i,r,a);
}
void Sift(int *b,int l,int r)
{
int i=l;
int x=*(b+i);
int j=i+i;
//if((j<2)&&(*(b+j)<*(b+j+1))) j++;
//while (j<=r&&(x<*(b+j)))
//{
while(j<=r)
{
if(j<r&&(*(b+j)<*(b+j+1)))
j++;
if(x>=(*(b+j)))
break;
*(b+i)=*(b+j);
i=j-1;
j=2*j;
//if((j<2)&&(*(b+j)<*(b+j+1))) j++;
}
*(b+i)=x;
}
void Sift1(int m,int *b)
{
int max;
int k;
int l=-1;
if(m%2==1) k=(m-1)/2;
else k=m/2;
//if(m<1) return;
//while(l<m-1)
//{
while(k>0)
{
if(2*k+2>m-1) return;
else if(2*k+1>m-1) return;
else if(2*k+1==m-1)
{
if(*(b+k)<*(b+2*k+1))
{
max=*(b+k);
*(b+k)=*(b+2*k+1);
*(b+2*k+1)=max;
}
}
if(*(b+2*k+1)<*(b+2*k+2))
{
if(*(b+k)<*(b+2*k+2))
max=*(b+k);
*(b+k)=*(b+2*k+2);
*(b+2*k+2)=max;
}
else
if(*(b+k)<*(b+2*k+1))
{
max=*(b+k);
*(b+k)=*(b+2*k+1);
*(b+2*k+1)=max;
}
k-=1;
}
//l++;
//}

}
void HeapSort(int m,int *b)
{
int i,*x;
x=new int[1];
//if (m%2==0) i=m/2;
//else i=(m+1)/2;
//for(i=m/2+1;i>1;i–)
//    Sift(b,i-1,m-1);
//if (m%2==0) i=m/2;
//else i=(m+1)/2;
for (i=m;i>1;i–)
{

Sift1(i,b);
*x=*(b+i);
*(b+i)=*(b+0);
*(b+0)=*x;
}
}
void Sift2(int b[],int l,int r)
{
int i=l;
int x=b[i];
int j=2*i+1;
if((j<r)&&(b[j]<b[j+1])) j++;
while((j<=r)&&(x<b[j]))
{
b[i]=b[j];
i=j;
j=2*i+1;
if((j<r)&&(b[j]<b[j+1])) j++;
}
if(i!=l) b[i]=x;
}

void HeapSort2(int m,int b[])
{
for(int i=m/2-1;i>=0;i–)
Sift(b,i,m-1);
for(i=m-1;i>0;)
{
int x=b[i];
b[i]=b[0];
b[0]=x;
Sift(b,0,–i);
}
}

February 1, 2011

Heap sorting.C++ Programming code


void Sift(int b[],int l,int r)
{
int i=l;
int x=b[i];
int j=2*i+1;
if((j<r)&&(b[j]<b[j+1])) j++;
while((j<=r)&&(x<b[j]))
{
b[i]=b[j];
i=j;
j=2*i+1;
if((j<r)&&(b[j]<b[j+1])) j++;
}
if(i!=l) b[i]=x;
}

void HeapSort(int m,int b[])
{
for(int i=m/2-1;i>=0;i–)
Sift(b,i,m-1);
for(i=m-1;i>0;)
{
int x=b[i];
b[i]=b[0];
b[0]=x;
Sift(b,0,–i);
}
}