# Programmer shizzies

### #2

Posted 14 April 2012 - 03:00 PM

**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.

### #6

Posted 14 April 2012 - 03:45 PM

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.//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?

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.

### #7

Posted 14 April 2012 - 03:55 PM

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.My naming convention was flawed initially as I called matrixType just matrix and it sounded more like a variable than a class.

### #9

Posted 14 April 2012 - 06:39 PM

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.

### #10

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.

### #11

Posted 28 April 2012 - 10:32 AM

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.

Motown Philly's back again

### #12

Posted 28 April 2012 - 10:33 AM

### #13

Posted 28 April 2012 - 10:38 AM

### #14

Posted 28 April 2012 - 12:26 PM

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.

believe you mean complexity n^2 instead of n^n.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).

Motown Philly's back again

### #15

Posted 28 April 2012 - 10:48 PM

believe you mean complexity n^2 instead of n^n.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).

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

# Reply to this topic

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users