Member Avatar for Dani

The attached program performs a QuickSort in C++ which sorts an array of structs based on their data members. Basically, it sorts an array of coordinates based on their distance from the origin.

/****************************/
/** Dani Horowitz ***********/
/** CSC120 Quick Sort Lab ***/
/** Dr. Kamberova ***********/
/****************************/

/*****************************************************************/
/** I have neither given nor received assistance in this lab *****/
/** I have read and agreed to Hofstra's academic honesty code ****/
/*****************************************************************/

// quick sort using a random pivot point on array of Points (x,y)
// the Points are sorted according to their distance from the origin (0,0)

#include "stdinc.h"
#include "point.h"

void makeArray(Point*, int);					// generates coordinates in an array
void printArray(Point*, Point*, int);			// prints unsorted and sorted arrays
int randInt(int, int);							// returns random int between two bounds
void quickSort(Point*, int, int);				// randomized quick sort algorithm
void Swap(Point*, int, int);					// swaps two points in an array
int Partition(Point*, int, int);				// partitions array at a randomized pivot

/********** BEGIN DRIVER FUNCTION **********/

// pre: none
// post: sorts array of randomly generated Points in order of distance from the origin
int main()
{
	int n;										// number of points in the array
	Point *P, *Q;								// dynamic arrays of points

	cout << "\nHow many points would you like the computer to generate? ";
	cin >> n;

	P = new Point[n];							// allocate space for P of n Points
	Q = new Point[n];							// allocate space for Q of n Points

	makeArray(P, n);							// create space for P of n Points
	for (int i = 0; i < n; i++) Q[i] = P[i];	// copy array P into array Q

	quickSort(P, 0, n - 1);						// sort array P
	if (n <= 25) printArray(Q, P, n);			// if <=25 Points, print arrays Q and P
	else cout << "\nTable will only be printed with 25 or fewer points.\n";

	delete [] P;								// free space allocated for P and Q
	delete [] Q;

	char again;									// run program again with user input
	cout << "\nWould you like to generate a new array? (Y/N) ";
	cin >> again;
	if (again == 'Y') main();

	cout << endl;
	return 0;									// successful completion
}

/********** END DRIVER FUNCTION **********/

// pre: empty array of Points and length of array
// post: fills array with randomly generated Points
void makeArray(Point* P, int n)
{
	for (int i = 0; i < n; i++)
	{
		P[i].x(randInt(0,99));
		P[i].y(randInt(0,99));
	}
	return;
}

// pre: two arrays of Points (one unsorted, one sorted) and their length
// post: neatly prints out arrays in table form
void printArray(Point* unsorted, Point* sorted, int n)
{
												// prints the unsorted array of points
	cout << "\n\nThe Original Array of Randomly Generated Points:\n\n";
	cout << "\n\tIndex\tPoint\t\tDistance From Origin\n";
	cout << "\t--------------------------------------------\n";
	for (int i = 0; i < n; i++)
	{
		cout << "\t" << i << "\t" << unsorted[i]
		<< "\t\t" << unsorted[i].dist_origin() << endl;
	}

												// prints the sorted array of points
	cout << "\n\nThe New Sorted Array of Randomly Generated Points:\n\n";
	cout << "\n\tIndex\tPoint\t\tDistance From Origin\n";
	cout << "\t--------------------------------------------\n";
	for (int i = 0; i < n; i++)
	{
		cout << "\t" << i << "\t" << sorted[i]
		<< "\t\t" << sorted[i].dist_origin() << endl;
	}
	return;
}

// pre: an upper and lower bound
// post: generates a random integer between upper and lower bound
int randInt(int lo, int hi)
{
	return int( 0.5 + lo + (1 - double(rand()) / RAND_MAX) * (hi - lo) );
}

// pre: an array of Points, a lower index bound, an upper index bound
// post: implements the quick sort algorithm between the bounds
void quickSort(Point* P, int p, int r)
{
	if (p >= r) return;							// base case for recursive algorithm
	int q = Partition(P, p, r);					// partition array at pivot point
	quickSort(P, p, q - 1);						// sort first half of array
	quickSort(P, q + 1, r);						// sort second half of array
	return;
}

// pre: an array of Points, two indices in the array
// post: swaps the values in two cells of the array
void Swap(Point* P, int a, int b)
{
	Point temp = P[a];
	P[a] = P[b];
	P[b] = temp;
	return;
}

// pre: an array of Points, a lower index bound, an upper index bound
// post: creates a random pivot point and swaps cells to accomidate for the pivot
int Partition(Point* P, int p, int r)
{
	int pivotPosition = randInt(p, r);			// random pivot point
	Swap(P, pivotPosition, r);					// put pivot at end of array
	pivotPosition = p - 1;						// place floating pivot at head of array
	Point pivot = P[r];							// value of pivot Point
	for (int i = p; i <= r - 1; i++)			// move everything if need be around pivot
	{
		if (pivot > P[i])
		{
			pivotPosition++;
			Swap(P, i, pivotPosition);
		}
	}
	Swap(P, r, pivotPosition + 1);
	return (pivotPosition + 1);					// return current pivot location
}
#include "point.h"
#include "stdinc.h"

Point::Point()									// constructor initializes (0,0)
{
	x_ = 0;
	y_ = 0;
}

int Point::x()									// returns the x-coord
{ return x_; }

void Point::x(int xcoord)						// sets x-coord to given value
{ x_ = xcoord; }

int Point::y()									// returns the y-coord
{ return y_; }

void Point::y(int ycoord)						// sets the y-coord to given value
{ y_ = ycoord; }

float Point::dist(Point p)						// computes distance to point p
{
	float delta_x = float( (this->x_ - p.x_) );
	float delta_y = float ( (this->y_ - p.y_) );
	return sqrt(delta_x * delta_x + delta_y * delta_y);
}

float Point::dist_origin()						//computes distance to origin
{ return sqrt(this->x_ * this->x_ + this->y_ * this-> y_); }

bool operator> (Point &p, Point &q)				// overloads > operator
{
	bool distance = false;
	if ( p.dist_origin() > q.dist_origin() )
		distance = true;
	return distance;
}

ostream& operator <<( ostream& os, Point& pt )	// overloads << operator
{
	os << "(" << pt.x() << "," << pt.y() << ")";
	return os;
}
class Point
{
public:
	Point();				// constructor that takes no arguments
	int x();				// returns the x-coordinate
	void x(int);			// sets the x-coordinate to the input value
	int y();				// returns the y-coordinate
	void y(int);			// sets the y-coordianate to the input value
	float dist(Point);		// returns distance to the input point
	float dist_origin();	// returns distance to the origin
private:
	int x_;					// internal rep is two integers, x_ for the
	int y_;					// x-coord and y_ for the y-coord
};

bool operator> (Point &p, Point &q);		// compares two points
#include <iostream.h>						// overload << to print a point
ostream& operator <<( ostream&, Point&);
// includes standard libraries and defines some constants
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

const int nil = 0;
const float
	maxfloat = 100000.0;
  • 5 Contributors
  • 8 Replies
  • 416 Views
  • 7 Months Discussion Span
  • Latest Post Latest Post by Chainsaw
cosi commented: Dani, meticulous coding. I like your style! :) +1

Recommended Answers

All 8 Replies

Member Avatar for Paladine

Nice Inline Commenting! Bravo on Code Format as well.

:-)

Member Avatar for Dani

Thank you ... I have a very definitive coding style.

Member Avatar for Bob

I would argue that your code suffers from excessive commenting, which is as bad as under-commenting. I also have a personal preference for avoiding end-of-line comments in all but the simplest of cases, but that's personal preference.

Let's look at some examples:

> int n; // number of points in the array

OK, so here you've declared an integer variable and given it the identifier 'n'. Because 'n' is devoid of meaning you have a comment alongside the declaration so that the reader knows what 'n' is for. So now what do you do? Do you comment the use of 'n' every time it's used in your program? Or do you expect the reader to remember, or to search the code for the declaration and comment? ...

> ...
> cin >> n;
> ...
> Q = new Point[n]; // allocate space for Q of n Points

Hmmm, how about calling it something other than 'n', for instance, let's call it 'numberOfPoints'. Now lets' look at the resulting changes to the code:

int numberOfPoints;
...
cin >> numberOfPoints;
...
Q = new Point[numberOfPoints];

Notice how the identifier conveys meaning, and you no longer need to comment the declaration or use of the variable.

Single character identifiers should generally be reduced to use only for loop indexes and the like, and even then there is often value in using a meaningful name.

There are various other examples where you need to let the code do the talking, and cases where the code already does but you use a comment in addition to the code, which is quite unecessary.


Another point, there are several ways to handle accessors (getters and setters) and this is one:

> int x(); // returns the x-coordinate
> void x(int); // sets the x-coordinate to the input value

but using the same overloaded function name for getting and setting can lead to confusion. Probably simpler and clearer is:

int getx();
void setx(int);

The comments are no longer necessary, and reading the code where the functions are called is easier on the reader.

>return 0; // successful completion

Why comment it? Returning zero means successful termination. If you really want to be clear you can always return EXIT_SUCCESS from <cstdlib> instead but return 0 should be enough.

You're still using the outdated C++ headers, which is a shame.

Also, C++ comes with a swap function so you don't need to roll your own.

> if (again == 'Y') main();

This is a real no-no. In C++ it's illegal to call main(). Don't do it. There are other ways to re-run the code inside main.


> int n;
> cin >> n;
> P = new Point[n];

Sooner or later someone using your program will enter a letter or something else other than a number, and then it will probably crash the program, because cin goes into a failed state. You should code against this.

There are other issues, but that's probably enough ;)
HTH

Member Avatar for Dani

Ahh! :( You sure do know how to break a gal down, eh? ;) (just kidding)

Okay okay where shall I start. First, this program was written my third semester at Hofstra for a data structures and algorithms course. (It was a theoretical course; the C++ was simply an exercise). It was a homework assignment meant to demonstrate my knowledge of the QuickSort. It was basically a "sort coordinates via a quicksort, exercise for a weekend" given Friday due Monday type deal. Now that I actually think back to it, I think we had a week for it.

As for over-commenting, I know I did ;) Basically I was taught right off the bat that over-commenting is great and deserves extra commendation for effort. In retrospect, my freshman professors might have told me so simply because it's easier for them to grade algorithms instead of teaching the best coding style. Of course, commenting is also a great way to learn computer programming. My current commenting style includes a detailed (probably too detailed) pre and a post above all functions/methods and very little else. (I'll use a pre and post even for one line functions that are plainly obvious, if for nothing else than consistancy for all functions). Alternatively, I'll comment function prototypes in my header files.

As for using better variable/function names ... I definitely see the point of this. I try to do it as much as I can (now) but I'm often guilty, unfortunately. I especially appreciate setx and getx as I have recently dealt with set and get blocks in C#.

To quote you ... "that's probably enough" ... my hand is getting tired of typing ;)

- Dani

P.S. Thanks for the post! :) No, really, thanks :)

Member Avatar for jayant

Its good to over-comment when explaining to noobs.
But, in a firm, when you work, the people there won't pay/reward you more for over-commenting. All they are interested in is work (the code) and has comments just enough for a programmer to be able to understand what it does.
Personally I avoid commenting as until essential (may use variable/function names upto 20 characters).
Writing the code with those small variables only, then do a replace all :D
my var names also tend to be long since I don't use Hungarian notation (M$ one), I use the old one.
I use this_is_my_string instead of sThisIsMyString

Its been over one year since I touched C++. Just took a 3 months gap from it after 6 years, but got extended to 1 yr. Will only be able to resume in Jan04.

Member Avatar for Bob

Ahh! :( You sure do know how to break a gal down, eh? ;) (just kidding)

All meant as constructive comment of course - I'm sure you know me well enough by now to know that ;)

Member Avatar for Dani

Yes, definitely :) That's why I threw the j/k in there!

Member Avatar for Chainsaw

Some of Bob's points are valid, but I'd like to sugest alternate comments.....

First, I like end-of-line comments that talk about THAT line. And I like separate-line comments that talk about the strategy of the next several lines. Like:

// Get the two numbers and sort them into order
-vs-
if (n % 2) // is n odd?

I agree with Bob on the variable names, depending on the SCOPE of the name. If I'm in a small loop, who cares if I use 'i' rather than 'loopIndex'?

for (int i = 0; i < 10; i++)

(note the time-honored tradition of FORTRAN use of i,j,k as integers!)

But, overall, if I could offer one piece of advice from 25 years of making a living writing code, and I know this is generally the OPPOSITE what we are taught in CS....

You need to understand your own code. The person who comes along a year from now doesn't matter. You have no control over that person, only over your own work. The quality of your work is based on your understanding of it, not on someone else's.

You will be judged based on the finished product, not on the variable names or brace style or the editor you used or whether you use overloaded operators or not.

Further, in all companies I know of, the SHIP DATE is the master. Not quality, not features. If you miss the ship date, don't tell your boss "But, we were delayed because we are staying away from multiple inheritence, just like the guidelines said!" Nor, "rather than coding an array we spent lots of time coding circular lists." :D

ok, so the bottom line for me, then, is:

CSCGal, were you happy with this work at the time? Were the consumers of this code happy?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.