heapsort help please!

This is a discussion on heapsort help please! within the C++ Programming forums, part of the General Programming Boards category; can someone tell me why the heapsort will not sort correctly in the code below. It works but does not ...

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    2

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

  2. #2
    Rabble Rouser Slacker's Avatar
    Join Date
    Dec 2005
    Posts
    116
    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!

  3. #3
    Registered User
    Join Date
    Dec 2005
    Posts
    2
    Thank you very much. This was making me crazy.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Heapsort
    By myle in forum C++ Programming
    Replies: 5
    Last Post: 06-26-2008, 02:44 AM
  2. Heapsort
    By xENGINEERx in forum C Programming
    Replies: 2
    Last Post: 03-30-2008, 08:17 PM
  3. Heapsort
    By abalfazl in forum C Programming
    Replies: 2
    Last Post: 08-06-2005, 07:11 PM
  4. heapsort problem...
    By talz13 in forum C++ Programming
    Replies: 9
    Last Post: 09-23-2003, 05:06 PM
  5. heapsort help plz
    By nsssn73 in forum C# Programming
    Replies: 0
    Last Post: 06-02-2002, 07:54 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21