heapsort problem...

• 09-22-2003
talz13
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); }```
• 09-22-2003
glUser3f
hmm, first why don't you remove unnecessary code from your post, you'll likely get more replies if you do so.
• 09-22-2003
velius
It would appear to be that the for loop condition to break should be i < 0 not i < 1.
• 09-22-2003
talz13
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?
• 09-23-2003
velius
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].
• 09-23-2003
talz13
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,
• 09-23-2003
velius
That is the result your looking for, isn't it?
• 09-23-2003
talz13
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)
• 09-23-2003
swoopy
> quicksort(a, 0, n);
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);         } }```
• 09-23-2003
talz13
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!