Jump to content


Photo

Programmer shizzies


261 replies to this topic

#1 mooniniteG

mooniniteG

    Sleeveless

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 13,086 posts
  • Location:Seattle, WA

Posted 14 April 2012 - 02:47 PM

Give me a few minutes and I'll check it out.
  • 1
DNa7A7D.jpg

#2 mooniniteG

mooniniteG

    Sleeveless

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 13,086 posts
  • Location:Seattle, WA

Posted 14 April 2012 - 03:00 PM

A couple of things that look wrong:

Ln 19 - The compiler is expecting matrix to be a type, but it's not declared anywhere. From your comment, this is supposed to be your ctor. Change it to:

void matrixType()

I'm not sure I follow what you're trying to do with the [][] here.

Ln 21/23/25 - Again, you're using matrix instead of matrixType.

Ln 60 - There's an end to a C-style comment (i.e. */) that isn't matched with a starting /*; delete it.

Ln 71 - Need to add matrixType:: before getSize since it's a member function.

Fixing these should help clear up any remaining warnings and errors.
  • 1
DNa7A7D.jpg

#3 juef

juef

    Shizz Captain

  • Members
  • PipPipPipPipPipPipPip
  • 1,067 posts
  • Location:Quebec, Canada

Posted 14 April 2012 - 03:00 PM

Looked quickly, but I believe there's some places where you probably meant 'matrixType' rather than 'matrix'. But hey, I haven't touched C++ in a while, so you'd probably be best wait for mooniniteG's reply!

[EDIT] Sniped! :)
  • 2

#4 Rize

Rize

    Shizz Gawd

  • Members
  • PipPipPipPipPipPipPipPipPipPip
  • 11,254 posts
  • Location:Baton Rouge

Posted 14 April 2012 - 03:29 PM

If you still have errors you can't fix, post the compiler errors along with the source code!
  • 1

#5 auriplane

auriplane

    Shizz Captain

  • Members
  • PipPipPipPipPipPipPip
  • 1,322 posts

Posted 14 April 2012 - 03:40 PM

Note that arrays aren't pointers.
  • 0

#6 mooniniteG

mooniniteG

    Sleeveless

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 13,086 posts
  • Location:Seattle, WA

Posted 14 April 2012 - 03:45 PM

//Constructor
matrixType::matrixType()
{
row = 0;
col = 0;

matrix[row][col];
}


Which I think is correct, since row and col were delcared as private ints the constructor will initialize them to 0 and use them as the values for the matrix. Then when the setSize method is called with the corresponding matrix passed as a parameter it will then change row and col to the user-specified sizes. Right?

matrix[row][col] doesn't set the size of the matrix, it will return the value at that index. You just have matrix defined as a pointer to a pointer to an int and it's never initialized to anything meaninful so deferencing it is going to result in undefined behavior.

If matrix doesn't need to have its sized changed, I'd hardcode the size to whatever is necessary for your assignment. Otherwise I'd template the size of the matrix, but you're probably not at the point of using templates yet.
  • 0
DNa7A7D.jpg

#7 juef

juef

    Shizz Captain

  • Members
  • PipPipPipPipPipPipPip
  • 1,067 posts
  • Location:Quebec, Canada

Posted 14 April 2012 - 03:55 PM

My naming convention was flawed initially as I called matrixType just matrix and it sounded more like a variable than a class.

I believe it is considered a good coding practice to name a class with its first letter capitalized (e.g. Matrix). It could even have a member named 'matrix' with no problem.
  • 0

#8 Nick The Newbie

Nick The Newbie

    Shizz JediMaster

  • Members
  • PipPipPipPipPipPipPipPip
  • 4,444 posts

Posted 14 April 2012 - 04:01 PM

We all good here, or do you still need help?
  • 0

#9 mooniniteG

mooniniteG

    Sleeveless

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 13,086 posts
  • Location:Seattle, WA

Posted 14 April 2012 - 06:39 PM

Typically you'd want a 3x3 or a 4x4 matrix. Unfortunately you can't just have an adjustable size array. You do have a few options though:

1) Template your class to take in the array size. You could either take in 1 size or different sizes for the rows or columns, but I'm guessing you want a "square' matrix.

2) Dynamically allocate memory for the matrix on the heap using new[] and delete[].

3) Use an STL collection like a vector.

Can't say which one is the right option without knowing the specific requirements of the assignment. The best option is mostly like #1. Something like this should work:

template<int T>
class MatrixType
{
...stuff...
private:
int matrix[T][T];
};

Declare a 3x3 matrix like this:

MatrixType<3> myMatrix;

I don't use C++ very frequently these days, so my syntax could be wrong here. There should be plenty of references online if you need to use them.
  • 1
DNa7A7D.jpg

#10 Nick The Newbie

Nick The Newbie

    Shizz JediMaster

  • Members
  • PipPipPipPipPipPipPipPip
  • 4,444 posts

Posted 28 April 2012 - 03:55 AM

NEW QUESTION (that should be easier to answer):

Below are three functions, each for a different sorting method (bubble, selection and insertion). You'll notice two unused int variables numComps and numAssigns that are both initialized to 0. What I need to do is to have numComps increase by one for every comparison made and numAssigns increase by one for each assignment made. Then I need to output the results. I know how to increase them by one with numComps++ and numAssigns++ and then output it with cout << numComps << " ::: " << numAssigns; at the end of the loops, however I'm having a hard time figuring out where to put numComps++ and numAssigns++. It seems like wherever I do it just goes to the max number of items in the array or sits at one. Any help?

Spoiler


Well, firstly, that second for loop in bubble sort needs to have curly braces around what it's looping. Regardless of how many statements are being looped, they should always be wrapped by curly braces, even it it's just one statement. Same goes for if additional lines under if statements. ANYWAY, that being said, for bubble sort, since you need to check the number of comparisons, then you need to increment it right before that if statement, hence the need for curly braces to wrap that second for loop. On the phone, so it's a bitch to type, will look at the others later.
  • 3

#11 radne

radne

    Pimpin

  • Members
  • PipPipPipPipPip
  • 555 posts
  • Location:in my room

Posted 28 April 2012 - 10:32 AM

Haven't compiled it yet, but for your bubblesort:

For an array with 5000 items and the bubblesort code you posted (There are implementations that stop if no swaps are made in a given iteration that are slightly better)
12497500 comparisons is correct.

Analysis is as follows:
On the first iteration of the outer loop: 4999 comparisons are made since the inner loops runs from 0 to 4998
On the second iteration of the outer loop: 4998 comparisons are made since the inner loops runs from 0 to 4997
On the third iteration of the outer loop: 4997 comparisons are made since the inner loop runs from 0 to 4996

.
.
On the final iteration, only 1 comparison is made..

The total number of comparisons is 1+2+3+4+5+...+4998+4999 = (5000)(4999)/2 = 12497500*

In general for an n item array you have 1+2+3+4...+(n-1) = n*(n-1)/2 comparisons with this bubblesort.
The number of assignments (swaps) is dependent on the data itself.
  • 1
"AIGHT , a bbig penis for MoonightGThang aand myoer MIG PICS, l lovooove me some chidlsbreading hips, m m mgood" -- Sherv

Motown Philly's back again

#12 XMark

XMark

    Sleeveless

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 12,201 posts
  • Location:Vancouver, BC

Posted 28 April 2012 - 10:33 AM

A bubble sort of 5000 elements will typically end up in a huge number of comparisons. For most cases, bubble sort is one of the least efficient sorting methods.
  • 1

#13 Rize

Rize

    Shizz Gawd

  • Members
  • PipPipPipPipPipPipPipPipPipPip
  • 11,254 posts
  • Location:Baton Rouge

Posted 28 April 2012 - 10:38 AM

A back of the napkin calculation: a quick sort has complexity of n log n which is what makes it special... any sorts you're studying leading up to quick sort are going to be n^n sorts (n to the n power). So 5000 elements will be 5000^5000 or 25,000,000 iterations of a loop. Your value of half that for bubble sort is very reasonable. It probably has an optimization that makes it's complexity (n^n)/2 which is a slight improvement, but still incredibly huge compared to n log n (which would be about 5000 * 12.5 or 62,500).
  • 1

#14 radne

radne

    Pimpin

  • Members
  • PipPipPipPipPip
  • 555 posts
  • Location:in my room

Posted 28 April 2012 - 12:26 PM

Just reposting your code with indenting and code tags
Spoiler


I believe your bubblesort is fine.

Your selection sort, as is, does not sort the array. This is because your inner for loop only does one thing: numComps++. Use braces to clearly define what you want to be looped.

For Insertion Sort, I believe (not 100% sure on this) that list[location - 1] > temp in the while loop should count as a comparison. So you may have to increment numComps inside the do loop as well.

Suggestion: Test on a small array, say 5 or 6 elements. Count comparisons and assignments by hand and using the code you implemented. They should match up. Also you should gain a better understanding of how each algorithm works. Also print out your array before sorting and after sorting to make sure it's actually sorted.



A back of the napkin calculation: a quick sort has complexity of n log n which is what makes it special... any sorts you're studying leading up to quick sort are going to be n^n sorts (n to the n power). So 5000 elements will be 5000^5000 or 25,000,000 iterations of a loop. Your value of half that for bubble sort is very reasonable. It probably has an optimization that makes it's complexity (n^n)/2 which is a slight improvement, but still incredibly huge compared to n log n (which would be about 5000 * 12.5 or 62,500).

believe you mean complexity n^2 instead of n^n. Posted Image
  • 1
"AIGHT , a bbig penis for MoonightGThang aand myoer MIG PICS, l lovooove me some chidlsbreading hips, m m mgood" -- Sherv

Motown Philly's back again

#15 Rize

Rize

    Shizz Gawd

  • Members
  • PipPipPipPipPipPipPipPipPipPip
  • 11,254 posts
  • Location:Baton Rouge

Posted 28 April 2012 - 10:48 PM

A back of the napkin calculation: a quick sort has complexity of n log n which is what makes it special... any sorts you're studying leading up to quick sort are going to be n^n sorts (n to the n power). So 5000 elements will be 5000^5000 or 25,000,000 iterations of a loop. Your value of half that for bubble sort is very reasonable. It probably has an optimization that makes it's complexity (n^n)/2 which is a slight improvement, but still incredibly huge compared to n log n (which would be about 5000 * 12.5 or 62,500).

believe you mean complexity n^2 instead of n^n. Posted Image


lol, yep. that was a rookie mistake! I meant n*n complexity which of course is n^2 not n^n. Obviously I did it properly when I came up with 25 million. I tried calculating 5000^5000 on a few online calculators just now for kicks. they report "infinity" as the result :lol:
  • 1



Reply to this topic



  


0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users