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