Thread: heapsort help please!

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

There's no need to post anything but the relevant functions. Any more just clutters things up and makes it harder to find what I need to help you. As to the problem at hand, you're trying to be too clever in HeapSort. It's way easier if you separate the first heapify step from the second extraction step:

Code:

void HeapSort (int a[], int n)
{
  for(int k=n/2-1; k>=0; k--)
  {
    Sift(a,k,n);
  }

  while (--n>0)
  {
    int x=a[0];
    a[0]=a[n];
    a[n]=x;
    Sift(a,0,n);
  }
}

Other than that you're solid.

Cheers!

Thank you very much. This was making me crazy.