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