-
Sort Function
Hey,
Can anyone help me with the development of the below sortPercentage function?
Code:
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include "dataobject.h"
using namespace std;
int randNum();
template <class iterator>
void sortPercentage(iterator start, iterator finish, int percentage);
template <class iterator>
void sortContainer(iterator start, iterator finish, int gap);
int randNum()
{
// rand() produces pseudo-random number in range 0 to RAND_MAX
// for most compilers RAND_MAX is 2^15-1
// randNum() produces pseudo-random number in range 0 to 2^31-1
return ((rand() << 16) + rand());
}
template <class iterator>
void sortPercentage(iterator start, iterator finish, int percent);
{
/************************************************** ***********************\
sortPercentage
Checks every consecutive pair of items in the container,
eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
and finds the percentage that are in order vs the total number of pairs.
This percentage value is returned.
\************************************************* ************************/
}
template <class iterator>
void sortContainer(iterator start, iterator finish, int gap)
{
/************************************************** **************\
Sort the container using shell sort
gap will be called with the original size of the container
The underlying sort for the container is bubble sort which
will be run twice for each gap decrement
\************************************************* ***************/
if (gap == 1) return;
iterator left, right;
int i, numswap, totswap=0, numpass, sortPercent;
gap = gap * 3 / 4;
do {
numswap = 0;
// Reduce gap. Gap will start out at half the size of the container
// Eventually will stabilize at 1 in size
gap = (gap * 2 + 1) / 3;
// make two passes through container with bubble sort
for (numpass=0; numpass<2; numpass++) {
right = left = start;
// Make the distance between left and right gap in size
for (i=0; i<gap; i++) right++;
// Make a pass through container using Bubble sort
while (right != finish) {
if (*left < *right) {
swap(left, right);
numswap++;
}
left++;
right++;
}
// update some statistics and print them
totswap += numswap;
cout << "gap = " << gap << " num swaps = " << numswap;
cout << " sort percentage = " << sortPercent(start, finish) << "\n";
if (numswap == 0) break;
}
} while (numswap > 0 || gap > 1);
cout << "Total swaps = " << totswap << "\n";
}
int main(int argc, char *argv[])
{
const int MAXDATA = 10000;
vector<dataObject> array;
dataObject *doPtr;
int i, rand;
try {
/************************************************** ************\
Initialise things to demonstrate the sort
\************************************************* *************/
// fill vector with unique values
for (i=0; i<MAXDATA; i++) {
doPtr = new dataObject(i);
array.push_back(*doPtr);
delete doPtr;
}
// set up random number generator
if (argc != 2) {
cout << "Syntax : program seed\n";
cout << "seed is any integer value\n";
return 0;
}
int seed = atoi(argv[1]);
srand(seed);
// scramble vector
for (i=0; i<MAXDATA; i++) {
rand = randNum() % MAXDATA;
swap(array[i], array[rand]);
}
cout << MAXDATA << " Items in vector\n";
/************************************************** ***********\
sort the vector using iterators
\************************************************* ************/
cout << "Sorting vector using shell sort\n";
sortContainer(array.begin(), array.end(), array.size());
} catch(...) {
cout << "\nERROR - undefined Exception thrown\n";
exit(1);
}
return 0;
}
Code:
#ifndef DATAOBJECT_H_
#define DATAOBJECT_H_
#include <algorithm>
/************************************************** *********\
class for holding data to be stored in container objects
\************************************************* **********/
struct dataObject
{
int keyval;
/************************************************** ******\
place any other data declartions the data object
may need here
\************************************************* *******/
/************************************************** ******\
constructors
\************************************************* *******/
// constructor
dataObject() : keyval(-1) {}
dataObject(int val) : keyval(val) {}
// copy constructor
dataObject(const dataObject &other) : keyval(other.keyval) {
// copy any data in other to this
}
/************************************************** ******\
misc functions
\************************************************* *******/
void swapObjects(dataObject &other) {
std::swap(keyval, other.keyval);
// swap any other data in dataObject
}
bool isKeyval(int val) const {
return (val == keyval);
}
int getKeyval() const {
return keyval;
}
int getHashval(int range) const {
return (keyval % range);
}
bool empty() const {
return (keyval == -1);
}
/************************************************** ******\
overloaded operators
\************************************************* *******/
// overloaded assignment operator
dataObject& operator = (const dataObject &other) {
dataObject temp(other);
swapObjects(temp);
return *this;
}
// overloaded relational operators
bool operator == (const dataObject &other) const {
return (keyval == other.keyval);
}
bool operator != (const dataObject &other) const {
return (keyval != other.keyval);
}
bool operator > (const dataObject &other) const {
return (keyval > other.keyval);
}
bool operator < (const dataObject &other) const {
return (keyval < other.keyval);
}
bool operator >= (const dataObject &other) const {
return (keyval >= other.keyval);
}
bool operator <= (const dataObject &other) const {
return (keyval <= other.keyval);
}
};
#endif
-
Code:
template <class iterator>
void sortPercentage(iterator start, iterator finish, int percent /*???*/);
{
/************************************************** ***********************\
sortPercentage
Checks every consecutive pair of items in the container,
eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
and finds the percentage that are in order vs the total number of pairs.
This percentage value is returned.
\************************************************* ************************/
}
There are problems with the prototype but the implementation should be quite trivial.
-
Code:
template <class iterator>
int sortPercentage(iterator start, iterator finish);
Would the above be better?
-
Yes that looks better. You nees to make a start on the contents of the function now before we can give you much more help on it. As for the rest of it though - some other tips:
You're missing an opportunity to take advantage of random-access iterators, by using a loop to increment 'right' by 'inc' where you could be using std::advance.
Should 'swap' not swap *left and *right? Or does swapping iterators themselves actually do what you want? I must admit I've never tried that.
Comb Sort usually decreases the gap to 10/13ths of what it was each time rather than 2/3rds. You may find that often a lot of passes with a gap of 1 end up being required.
It's also highly unorthodox to make two passes through the data for each gap width, but I guess that could be how you're lessening the problem I just mentioned. I'm sure the normal way of implementing it works much better overall.
Don't new up and then delete something just to insert it into a vector:
Code:
for (i=0; i<MAXDATA; i++) {
doPtr = new dataObject(i);
array.push_back(*doPtr);
delete doPtr;
}
You should just be using the stack like this:
Code:
for (i=0; i<MAXDATA; i++) {
array.push_back(dataObject(i));
}
And finally, don't implement the assignment operator or copy-constructor (or destructor for that matter), for any class that will already do the right thing when these are left unimplemented. More code equals more room for bugs. If you add an other members to the class and forget to update both of these you'll get a bug that could take quite a while to track down. If you leave them unimplemented instead then they'll just continue to work. If at some point you later introduce a member that requires different copying behaviour (such as a raw pointer to an owned array), then that's the point at which you should perhaps implement these.
-
Would something like the below do the job properlly?
Its just the raw so I'd have to edit to fit it to the spec but I'm just trying to work out the logic first.
Code:
bool Changed = true;
int Passes = 0;
while(Changed)
{
if Changed = false;
passes++;
for(int j = 0; j < arraySize -1; j++)
{
if(a[j] > a[j+1])
{
Changed = true;
int hold = a[j];
a[j] = a[j+1];
a[j+1] = hold;
}
}
}
-
I think the idea is to not make any change to the array contents. As far as I can see it's supposed to return some measure of presortedness.
I think they just want you to count up the number of adjacent items that are out of order versus how many adjacent pairs there are.
-
Ok yeah I think you're right. So in that case I would just remove the swap function from the check right?
Code:
bool Changed = true;
int Passes = 0;
while(Changed)
{
if Changed = false;
passes++;
for(int j = 0; j < arraySize -1; j++)
{
if(a[j] > a[j+1])
{
Changed = true;
}
}
}
-
Closer. You want to actually count how many times, i.e. increment a count rather than simply setting something to true.
Then to get a percentage, you need to work out how many pairs of items there are.
Then you need a formula for percentage. Something like: 100 * count / total
-
Isn't the passes my count though?
Code:
bool Changed = true;
int Passes = 0;
while(Changed)
{
if Changed = false;
passes++;
for(int j = 0; j < arraySize -1; j++)
{
if(a[j] > a[j+1])
{
Changed = true;
}
}
}
percentage = passes / (arraysize -1) * 100
-
Why don't you compile and run your code?
The general logic might work, but why make it so complicated? Why manipulate a boolean in complicated way, when you can just increment a counter at the same place where you determine that it needs to be incremented.
Code:
percentage = passes / (arraysize -1) * 100
With integer math this might be always 0.
-
Code:
if Changed = false;
passes++;
Did you want this to be an if statement or what?
I also don't see why passes is a measure of presortedness. In that regard, sorting algorithms can take many "passes" more than what is optimal to sort something.
I guess I would implement insertion sort and then calculate using the lengths of the unsorted and sorted ends.
-
How else would I do it? I thought the boolean would be a good way.
-
You don't need that while loop, just the for loop - sorry I was ignoring that it was even there before. You only need to go through the array once from start to finish and count how many pairs were out of order.
anon is correct that you need to multiply by 100 before the division or else the last part evaulated will be either 0 * 100 or 1 * 100.
Another hint: You don't need to count the number of pairs there are, it's just one subtraction to get that answer.
-
So I've edited the code and it compiles but when I run it I get the below error:
./a.out 32
10000 Items in vector
Sorting vector using shell sort
Segmentation Fault (core dumped)
Any ideas on what I need to change so that I can get it to run?
Code:
/********************************************************\
Test program for demonstrating sorting algorithms
\********************************************************/
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include "dataobject.h"
using namespace std;
int randNum();
template <class iterator>
void sortContainer(iterator start, iterator finish, int gap);
int randNum()
{
// rand() produces pseudo-random number in range 0 to RAND_MAX
// for most compilers RAND_MAX is 2^15-1
// randNum() produces pseudo-random number in range 0 to 2^31-1
return ((rand() << 16) + rand());
}
template <class iterator>
int sortPercentage(iterator start, iterator finish)
{
/*************************************************************************\
sortPercentage
Checks every consecutive pair of items in the container,
eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
and finds the percentage that are in order vs the total number of pairs.
This percentage value is returned.
\*************************************************************************/
iterator left, right;
int InnerCount;
int comparisons;
int swaps = 0;
for (comparisons = 0; comparisons < finish; comparisons++)
{
for (InnerCount = 0; InnerCount < finish; InnerCount++)
{
right = left = start;
while (right != finish)
{
if (*left < *right)
{
swaps+=1;
}
}
}
comparisons+=1;
}
}
template <class iterator>
void sortContainer(iterator start, iterator finish, int gap)
{
/****************************************************************\
Sort the container using shell sort
gap will be called with the original size of the container
The underlying sort for the container is bubble sort which
will be run twice for each gap decrement
\****************************************************************/
if (gap == 1) return;
iterator left, right;
int i, numswap, totswap=0, numpass, sortPercent;
gap = gap * 3 / 4;
do {
numswap = 0;
// Reduce gap. Gap will start out at half the size of the container
// Eventually will stabilize at 1 in size
gap = (gap * 2 + 1) / 3;
// make two passes through container with bubble sort
for (numpass=0; numpass<2; numpass++) {
right = left = start;
// Make the distance between left and right gap in size
for (i=0; i<gap; i++) right++;
// Make a pass through container using Bubble sort
while (right != finish) {
if (*left < *right) {
swap(left, right);
numswap++;
}
left++;
right++;
}
// update some statistics and print them
totswap += numswap;
cout << "gap = " << gap << " num swaps = " << numswap;
// cout << " sort percentage = " << sortPercent(start, finish) <<
"\n";
if (numswap == 0) break;
}
} while (numswap > 0 || gap > 1);
cout << "Total swaps = " << totswap << "\n";
}
int main(int argc, char *argv[])
{
const int MAXDATA = 10000;
vector<dataObject> array;
dataObject *doPtr;
int i, rand;
try {
/**************************************************************\
Initialise things to demonstrate the sort
\**************************************************************/
// fill vector with unique values
for (i=0; i<MAXDATA; i++) {
doPtr = new dataObject(i);
array.push_back(*doPtr);
delete doPtr;
}
// set up random number generator
if (argc != 2) {
cout << "Syntax : program seed\n";
cout << "seed is any integer value\n";
return 0;
}
int seed = atoi(argv[1]);
srand(seed);
// scramble vector
for (i=0; i<MAXDATA; i++) {
rand = randNum() % MAXDATA;
swap(array[i], array[rand]);
}
cout << MAXDATA << " Items in vector\n";
/*************************************************************\
sort the vector using iterators
\*************************************************************/
cout << "Sorting vector using shell sort\n";
sortContainer(array.begin(), array.end(), array.size());
} catch(...) {
cout << "\nERROR - undefined Exception thrown\n";
exit(1);
}
return 0;
}
-
Okay I had just told you how "You don't need that while loop, just the for loop" but you've done the opposite of removing that loop - you've added yet another nested loop to the function.
I can also see from your latest code that you've actually completely ignored everything I have said.
So since when helped you if anything go backwards, I'm going to stop helping you now, in case by some miracle you then actually go forwards and get closer to the goal. Best of luck.