can someone tell me why the heapsort will not sort correctly in the code below. It works but does not sort in the correct order. The other sorts work fine....What am I missing? Thanks
Code:
//SortDriver.cpp Project: Sorts
# include <iostream>
using namespace std;
void BubbleSort(int a[], int n);
void SelectionSort(int a[], int n);
void InsertionSort( int a[], int n);
void HeapSort (int a[], int n);
void Display (int a[], int n);
void Swap(int&x,int&y);
void Sift(int a[],int k, int n);
void QuickSort (int a[],int n);
int main ()
{
int a[6]={3,5,9,8,1,7};
//BubbleSort (a,6);
//SelectionSort (a,6);
//InsertionSort (a,6);
HeapSort (a,6);
//QuickSort(a,6);
Display (a,6);
return 0;
}
void BubbleSort(int a[], int n)
{
int temp;
for (int i=0; i<n-1; i++)
{
for (int j=0; j<n-1;j++)
{
if (a[j]>a[j+1])
{
temp= a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
void SelectionSort(int a[], int n)
{
int location;
int minIndex;
int min;
for (int i=0; i<n-1;i++)
{
min=a[i];
for (location=i+1; location<n;location++)
{
if (a[location]<min)
{
minIndex=location;
min=a[location];
}
}
Swap(a[i], a[minIndex]);
}
}
void InsertionSort( int a[], int n)
{
int first;
int temp;
int location;
for (first=1; first<n; first++)
{
if (a[first]<a[first-1])
{
temp=a[first];
location=first;
do{
a[location]=a[location-1];
location--;
} while((location>0)&&(a[location-1]>temp));
a[location]=temp;
}
}
}
void HeapSort (int a[], int n)
{
int x;
for(int k=n/2-1; k>=0; k--)
{
while (--n>0)
{
x=a[0];
a[0]=a[n];
a[n]=x;
Sift(a,0,n);
}
}
}
void Swap(int&x,int&y)
{
int temp;
temp=x;
x=y;
y=temp;
}
void Sift(int a[],int k, int n)
{
int i=k;
int j=0;
int x=a[i];
while((j=2*i+1)<n)
{
if((j<n-1)&&(a[j]<a[j+1]))
j++;
if(x>=a[j])
break;
a[i]=a[j];
i=j;
}
a[i]=x;
}
void Display(int a[],int n)
{
for (int i=0; i<n; i++)
{
cout<<a[i]<<"-->";
cout<<"END\n";
}
}
void QuickSort (int a[],int n)
{
int i=0;
int j=n-1;
int temp=a[j/2];
int w=0;
do{
while (a[i] < temp)
i++;
while (a[j]>temp)
j--;
if (i<j)
{
w=a[i];
a[i]=a[j];
a[j]=w;
}
else
{
if (i==j)
{
i++;
j--;
}
break;
}
}while(++i<=--j);
if(j>0)
QuickSort(a,j+1);
if(i<n-1)
QuickSort(a+i,n-i);
}