heapsort problem...

This is a discussion on heapsort problem... within the C++ Programming forums, part of the General Programming Boards category; ok, i was going over this problem with my teacher, and she couldn't find what was wrong in the time ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    69

    heapsort problem...

    ok, i was going over this problem with my teacher, and she couldn't find what was wrong in the time we had.

    the problem is, my heapsort doesn't sort the first number in the vector. it skips over it and continues on with the rest of the vector, but forgets about the first value.

    the first thing i tried was changing 'n' to 'n-1' in my function call to heapsort, which got rid of another problem i had (it was grabbing some non-existent number before), but it still left the first number un-sorted.

    please see if anybody can find out what's wrong!

    Code:
    #include <iostream>
    #include <cstdlib>
    //#include <stdlib.h>
    #include <time.h>
    #include <vector>
    using namespace std;
    
    const int n=10;
    
    void new_vector(vector <int>&a);
    void random(vector <int>&a);
    void quicksort(vector <int>&a, int first, int last);
    int partition(vector <int>&a, int first, int last);
    /*precondition: before first call, the subarrays a[first...i] and a[i+1...j-1] are empty
    postcondition:	j=last when loop terminates, all elements of a are partitioned into one of: a[p...i]<=pivot, a[i+1...last-1]>pivot, and a[last]=pivot*/
    
    void max_heapify(vector <int>&a, int i, int n);
    void build_max_heap(vector <int>&a, int n);
    void heapsort(vector <int>&a, int n);
    
    void random_quicksort(vector <int>&a, int first, int last);
    int random_partition(vector <int>&a, int first, int last);
    
    //debug
    void output_vector(vector <int>a, int n)
    {
    	cout<<"The vector a contains:" <<endl;
    	for (int i=0;i<n;i++)
    	{
    		cout<<a[i] <<", ";
    	}
    	cout<<endl;
    }
    
    
    int main()
    {
    	int x=0;
    	time_t seconds;										//declare variable to hold second on clock
    	time(&seconds);										//get value from system clock and place in seconds variable
    //	cout<<"the time vaule used for this is: " <<seconds <<endl;
    	srand((unsigned int) seconds);						//convert seconds to an unsigned integer
    	vector <int> a;
    	random(a);
    
    	output_vector(a, n);
    	cout<<endl;
    	
    	heapsort(a, n);
    	cout<<"heapsort finished:" <<endl;
    	output_vector(a, n);
    	cout<<endl;
    	
    	quicksort(a, 0, n);
    	cout<<"quicksort finished:" <<endl;
    	output_vector(a, n);
    	cout<<endl;
    	
    	a.clear();
    	random(a);
    	cout<<"new vector contains:" <<endl;
    	output_vector(a, n);
    	cout<<endl;
    	
    	quicksort(a, 0, n);
    	cout<<"quicksort finished (2):" <<endl;
    	output_vector(a, n);
    	cout<<endl;
    
    	random_quicksort(a, 0, n);
    	cout<<"random quicksort finished:" <<endl;
    	output_vector(a, n);
    	cout<<endl;
    
    	a.clear();
    	random(a);
    	cout<<"new vector contains:" <<endl;
    	output_vector(a, n);
    	cout<<endl;
    
    	random_quicksort(a, 0, n);
    	cout<<"random quicksort finished (2):" <<endl;
    	output_vector(a, n);
    
    	a.clear();
    	cin>>x;
    	return 0;
    }
    
    void random(vector <int>&a)
    {
    	for(int j=0;j<n;j++)								//loops n times adding 
    	{
    		a.push_back(rand());
    	}
    }
    
    void quicksort(vector <int>&a, int first, int last)
    {
    	if (first<last)										//continues until first equals last
    	{
    		int pivot=partition(a, first, last);			//defines the pivot point
    		quicksort(a, first, pivot-1);					//recursive call to the left of pivot
    		quicksort(a, pivot+1, last);					//recursive call to the right of pivot
    	}
    }
    
    int partition(vector <int>&a, int first, int last)
    {
    	int x=a[last];										//define x as the value in 'last' position
    	int i=first-1;										//define i as 'first' -1
    	for (int j=first;j<last;j++)						//loops 'last'-'first' times
    	{
    		if (a[j]<=x)									//if the value of a[j] is less than the pivot point value
    		{
    			i=i+1;										//incrememt i
    			swap(a[i],a[j]);							//swap values in a[i] and a[j]
    		}
    	}
    
    	swap(a[i+1],a[last]);								// swap values in a[i+1] and a[last]
    	return i+1;											//returns the value of i+1, which 'pivot' is then set equal to
    }
    
    
    void max_heapify(vector <int>&a, int i, int n)
    {
    	int largest=0;
    	int l=2*i;
    	int r=(2*i)+1;
    	if ((l<=n)&&(a[l]>a[i]))
    	{
    		largest=l;
    	}
    	else
    	{
    		largest=i;
    	}
    	if ((r<=n)&&(a[r]>a[largest]))
    	{
    		largest=r;
    	}
    	if (largest!=i)
    	{
    		swap(a[i], a[largest]);
    		max_heapify(a, largest, n);
    	}
    }
    
    void build_max_heap(vector <int>&a, int n)
    {
    	for (int i=(n/2);i>0;i--)
    	{
    		max_heapify(a, i, n);
    	}
    }
    
    void heapsort(vector <int>&a, int n)
    {
    	build_max_heap(a, n);
    	for (int i=n;i>1;i--)
    	{
    		swap(a[1], a[i]);
    		max_heapify(a, 1, i-1);
    	}
    }
    
    void random_quicksort(vector <int>&a, int first, int last)
    {
    	if (first<last)
    	{
    		int random_pivot=random_partition(a, first, last);
    		random_quicksort(a, first, random_pivot-1);
    		random_quicksort(a, random_pivot+1, last);
    	}
    }
    
    int random_partition(vector <int>&a, int first, int last)
    {
    	int i=0;
    	time_t seconds;
    	time(&seconds);
    	srand((unsigned int) seconds);
    	i=(rand()%(last-first+1)+first);
    	swap(a[last], a[i]);
    	return partition(a, first, last);
    }

  2. #2
    Registered User glUser3f's Avatar
    Join Date
    Aug 2003
    Posts
    345
    hmm, first why don't you remove unnecessary code from your post, you'll likely get more replies if you do so.

  3. #3
    Master of the Universe! velius's Avatar
    Join Date
    Sep 2003
    Posts
    219
    It would appear to be that the for loop condition to break should be i < 0 not i < 1.
    While you're breakin' down my back n'
    I been rackin' out my brain
    It don't matter how we make it
    'Cause it always ends the same
    You can push it for more mileage
    But your flaps r' wearin' thin
    And I could sleep on it 'til mornin'
    But this nightmare never ends
    Don't forget to call my lawyers
    With ridiculous demands
    An you can take the pity so far
    But it's more than I can stand
    'Cause this couchtrip's gettin' older
    Tell me how long has it been
    'Cause 5 years is forever
    An you haven't grown up yet
    -- You Could Be Mine - Guns N' Roses

  4. #4
    Registered User
    Join Date
    Oct 2002
    Posts
    69
    ok, here's the code part that relates to the heapsort:

    Code:
    void max_heapify(vector <int>&a, int i, int n)
    {
    	int largest=0;
    	int l=2*i;
    	int r=(2*i)+1;
    	if ((l<=n)&&(a[l]>a[i]))
    	{
    		largest=l;
    	}
    	else
    	{
    		largest=i;
    	}
    	if ((r<=n)&&(a[r]>a[largest]))
    	{
    		largest=r;
    	}
    	if (largest!=i)
    	{
    		swap(a[i], a[largest]);
    		max_heapify(a, largest, n);
    	}
    }
    
    void build_max_heap(vector <int>&a, int n)
    {
    	for (int i=(n/2);i>0;i--)
    	{
    		max_heapify(a, i, n);
    	}
    }
    
    void heapsort(vector <int>&a, int n)
    {
    	build_max_heap(a, n);
    	for (int i=n;i>1;i--)
    	{
    		swap(a[1], a[i]);
    		max_heapify(a, 1, i-1);
    	}
    }
    and velius, which part are you talking about i<0 not i<1? can you clarify which loop that was in reference to?

  5. #5
    Master of the Universe! velius's Avatar
    Join Date
    Sep 2003
    Posts
    219
    Sorry, I meant i > 0 not i > 1. That was just bass ackwards typing.
    I think it is in the heapsort function. You pass to the swap function a[1]. You need to pass it a[0].
    Last edited by velius; 09-23-2003 at 04:47 AM.
    While you're breakin' down my back n'
    I been rackin' out my brain
    It don't matter how we make it
    'Cause it always ends the same
    You can push it for more mileage
    But your flaps r' wearin' thin
    And I could sleep on it 'til mornin'
    But this nightmare never ends
    Don't forget to call my lawyers
    With ridiculous demands
    An you can take the pity so far
    But it's more than I can stand
    'Cause this couchtrip's gettin' older
    Tell me how long has it been
    'Cause 5 years is forever
    An you haven't grown up yet
    -- You Could Be Mine - Guns N' Roses

  6. #6
    Registered User
    Join Date
    Oct 2002
    Posts
    69
    here's the output i get when i change those 1's to 0's:

    =====================
    The vector a contains:
    12734, 899, 22226, 31485, 3172, 5610, 23000, 24445, 16752, 19814,

    heapsort finished:
    The vector a contains:
    31485, 22226, 24445, 19814, 5610, 23000, 899, 16752, 3172, -842150451,

    quicksort finished:
    The vector a contains:
    -842150451, 899, 3172, 5610, 12734, 16752, 19814, 22226, 23000, 24445,
    =====================



    here is what i originally had, without modifying the function call or changing the 1's to 0's:
    =====================
    The vector a contains:
    14269, 6378, 29779, 3515, 1358, 16165, 11292, 24881, 11183, 13806,

    heapsort finished:
    The vector a contains:
    14269, -842150451, 1358, 3515, 6378, 11183, 11292, 13806, 16165, 24881,

    quicksort finished:
    The vector a contains:
    -842150451, 1358, 3515, 6378, 11183, 11292, 13806, 14269, 16165, 24881,

  7. #7
    Master of the Universe! velius's Avatar
    Join Date
    Sep 2003
    Posts
    219
    That is the result your looking for, isn't it?
    While you're breakin' down my back n'
    I been rackin' out my brain
    It don't matter how we make it
    'Cause it always ends the same
    You can push it for more mileage
    But your flaps r' wearin' thin
    And I could sleep on it 'til mornin'
    But this nightmare never ends
    Don't forget to call my lawyers
    With ridiculous demands
    An you can take the pity so far
    But it's more than I can stand
    'Cause this couchtrip's gettin' older
    Tell me how long has it been
    'Cause 5 years is forever
    An you haven't grown up yet
    -- You Could Be Mine - Guns N' Roses

  8. #8
    Registered User
    Join Date
    Oct 2002
    Posts
    69
    i'm still working on it with my teacher,

    but those results above aren't really sorted if you look at it...
    the first one, heapsort doesn't get sorted, in the second one, heapsort get sorted except for the first value and the garbage it pulls in (i noticed that the largest value in the vector gets replaced by the garbage in the second run down there)

  9. #9
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    > quicksort(a, 0, n);
    Instead try:
    quicksort(a, 0, n-1);


    Code:
    >void build_max_heap(vector <int>&a, int n)
    >{
    >	for (int i=(n/2);i>0;i--)
    >	{
    >		max_heapify(a, i, n);
    >	}
    >}
    
    Try:
    void build_max_heap(vector <int>&a, int n)
    {
    	for (int i=(n/2);i>=0;i--)
    	{
    		max_heapify(a, i, n-1);
    	}
    }
    Code:
    >void heapsort(vector <int>&a, int n)
    >{
    >	build_max_heap(a, n);
    >	for (int i=n;i>1;i--)
    >	{
    >		swap(a[1], a[i]);
    >		max_heapify(a, 1, i-1);
    >	}
    >}
    
    Try:
    void heapsort(vector <int>&a, int n)
    {
    	build_max_heap(a, n);
    	for (int i=n-1;i>=1;i--)
    	{
    		swap(a[0], a[i]);
    		max_heapify(a, 0, i-1);
    	}
    }

  10. #10
    Registered User
    Join Date
    Oct 2002
    Posts
    69
    those changes did help a bit, along with changing the rest of my function calls to 'n-1', now i don't have any garbage numbers coming in.

    hopefully the last problem, but with the new changes it misses the last number in heapsort. oh wait, i just fixed that one now... the last change i made to correct this problem was:

    Code:
    void heapsort(vector <int>&a, int n)
    {
    	build_max_heap(a, n);
    	for (int i=n;i>=1;i--)
    	{
    		swap(a[0], a[i]);
    		max_heapify(a, 0, i-1);
    	}
    }
    where i changed
    for(int i=n-1....)
    to
    for(int i=n....)

    well, problems solved! thanx!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM

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