//Heap Sort in C++ #include <iostream> #include <cstdlib> #include <ctime> #incl
ID: 3539920 • Letter: #
Question
//Heap Sort in C++
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <time.h>
using namespace std;
const int SIZE = 500000;
int x [SIZE];
void main ( )
{
int i;
//seed srand with different value each time you run
//so that rand will generate different sequence each time you run
srand((unsigned )time(NULL));
for ( i=0;i<SIZE;i++)
{
x[i]=rand();
}
//Calculate the time taken by a sort routine in seconds as below:
clock_t start, finish;
start =clock( ); //time in milliseconds
sort(x, SIZE );
finish=clock( ); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
double duration = ((double) (finish-start)) / CLOCKS_PER_SEC ;
cout<< duration <<endl; //time duration in seconds
}
//heap sort method
void sort ( int x [] , int length)
{
if (length < 2)
return;
//change unsorted array to heapified array
buildHeap (x, length );
//change heapified array to sorted array
sortHeap (x, length);
}
//Method below changes unsorted array into heapified array
//Pre-condition: length > 1
void buildHeap (int x [], int length)
{
int i;
for (lastIndex=1; lastIndex<length; lastIndex++)
{
reheapifyUpward (x, lastIndex);
}
}
//lastIndex is the index of the last working element of the array received.
void reheapifyUpward (int x [], int lastIndex)
{
int childIndex = lastIndex;
while (childIndex > 0 )
{
parentIndex = (childIndex-1)/2;
if (x [childIndex] <= x [parentIndex])
break;
else
{
//swap values at childIndex and at parentIndex.
//Update child to parent
childIndex = parentIndex;
}
}
}
//Method below changes heapified array into sorted array
//Pre-condition: length > 1
//lastIndex is the index of the last element of the array.
void sortHeap (int x [], int length)
{
int lastIndex = length - 1;
while (lastIndex > 0)
{
//swap the contents of index 0 with contents of lastIndex
//decrement the array size
lastIndex--;
//call reheapifyDownward. Pass it the array and the last index number of the array.
reheapifyDownward (x, lastIndex);
}
}
void reheapifyDownward (int x [], int lastIndex)
{
int parentIndex = 0;
while (parentIndex < lastIndex)
{
//findBigChildIndex will return a negative value if parent has no children.
bigChildIndex = findBigChildIndex (parentIndex, x, lastIndex);
if (bigChildIndex < 0 || x [bigChildIndex] <= x [parentIndex])
break;
else
{
//swap value at parentIndex with value at bigChildIndex
//update parentIndex
parentIndex = bigChildIndex;
}
}
}
//The function will return -1 if the parent had no children.
int findBigChildIndex (int parentIndex, int [ ] x, int lastIndex)
{
lChildIndex = (2 * parentIndex) + 1;
rChildIndex = (2 * parentIndex) + 2;
//case both children exist
if (rChildIndex <= lastIndex && lChildIndex <= lastIndex)
{
//compare value at rChildIndex and at lChildIndex
//return the index where the value is larger
}
//case only left child exist
else if (lChildIndex <= lastIndex)
{
return lChildIndex;
}
//case both children missing
else
{
return -1;
}
}
Explanation / Answer
//Heap Sort in C++
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <time.h>
using namespace std;
const int SIZE = 500000;
void sort ( int x [] , int length);
void buildHeap (int x [], int length);
void reheapifyUpward (int x [], int lastIndex);
void sortHeap (int x [], int length);
void reheapifyDownward (int x [], int lastIndex);
int findBigChildIndex (int parentIndex, int x[ ], int lastIndex);
int x [SIZE];
int main ( )
{
int i;
//seed srand with different value each time you run
//so that rand will generate different sequence each time you run
srand((unsigned )time(NULL));
for ( i=0;i<SIZE;i++)
{
x[i]=rand();
}
//Calculate the time taken by a sort routine in seconds as below:
clock_t start, finish;
start =clock( ); //time in milliseconds
sort(x, SIZE );
finish=clock( ); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
double duration = ((double) (finish-start)) / CLOCKS_PER_SEC ;
cout<< duration <<endl; //time duration in seconds
// below code is just to check un comment to see.
// whether array is really sorted or not
// for(int i=0; i<30; i++)
// cout << x[i] << " ";
return 0;
}
//heap sort method
void sort ( int x [] , int length)
{
if (length < 2)
return;
//change unsorted array to heapified array
buildHeap (x, length );
//change heapified array to sorted array
sortHeap (x, length);
}
//Method below changes unsorted array into heapified array
//Pre-condition: length > 1
void buildHeap (int x [], int length)
{
int i;
for (int lastIndex=1; lastIndex<length; lastIndex++)
{
reheapifyUpward (x, lastIndex);
}
}
//lastIndex is the index of the last working element of the array received.
void reheapifyUpward (int x [], int lastIndex)
{
int childIndex = lastIndex;
while (childIndex > 0 )
{
int parentIndex = (childIndex-1)/2;
if (x [childIndex] <= x [parentIndex])
break;
else
{
//swap values at childIndex and at parentIndex.
int temp = x[childIndex];
x[childIndex] = x[parentIndex];
x[parentIndex] = temp;
//Update child to parent
childIndex = parentIndex;
}
}
}
//Method below changes heapified array into sorted array
//Pre-condition: length > 1
//lastIndex is the index of the last element of the array.
void sortHeap (int x [], int length)
{
int lastIndex = length - 1;
while (lastIndex > 0)
{
//swap the contents of index 0 with contents of lastIndex
int temp = x[0];
x[0] = x[lastIndex];
x[lastIndex] = temp;
//decrement the array size
lastIndex--;
//call reheapifyDownward. Pass it the array and the last index number of the array.
reheapifyDownward (x, lastIndex);
}
}
void reheapifyDownward (int x [], int lastIndex)
{
int parentIndex = 0;
while (parentIndex < lastIndex)
{
//findBigChildIndex will return a negative value if parent has no children.
int bigChildIndex = findBigChildIndex (parentIndex, x, lastIndex);
if (bigChildIndex < 0 || x [bigChildIndex] <= x [parentIndex])
break;
else
{
//swap value at parentIndex with value at bigChildIndex
int temp = x[parentIndex];
x[parentIndex] = x[bigChildIndex];
x[bigChildIndex] = temp;
//update parentIndex
parentIndex = bigChildIndex;
}
}
}
//The function will return -1 if the parent had no children.
int findBigChildIndex (int parentIndex, int x[], int lastIndex)
{
int lChildIndex = (2 * parentIndex) + 1;
int rChildIndex = (2 * parentIndex) + 2;
//case both children exist
if (rChildIndex <= lastIndex && lChildIndex <= lastIndex)
{
//compare value at rChildIndex and at lChildIndex
//return the index where the value is larger
return (x[rChildIndex] > x[lChildIndex])?rChildIndex:lChildIndex;
}
//case only left child exist
else if (lChildIndex <= lastIndex)
{
return lChildIndex;
}
//case both children missing
else
{
return -1;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.