Jump to content


Photo

Programmer shizzies


285 replies to this topic

#16 Daemon9623

Daemon9623

    Shizz Overlord

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 18,936 posts
  • Location:Middle Earth

Posted 28 April 2012 - 10:13 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.

Hmm, I had the curly braces in there in my program, I must have copied a bit of old code. In any case, I put the numComps incrementor in right before the if statement and it's returning 12497500 comparisons. That seems a little high to me considering that there are only 5000 numbers in the array. This definitely looks like a step more in the right direction than what I had before, though. :)

edit: okay, here's the whole program. I'm supposed to make three arrays with 5000 identical random numbers (I am aware that the random numbers that get generated are the same random numbers every time with just the rand() function, but that's okay for this), so I create one array and populate it with random ints and then copy each index into the other arrays. Got that part no problem. Then I need to output the number of comparison and assignments that are made in each sorting method to see which ones perform more/less. The output at the end of the bubbleSort function is just a placeholder for how the output should look without polishing and it needs to go into the other functions as well. Like I said before, my problem is that I'm not sure where to put the incrementors for the numComps and numAssigns variables to get the right numbers.
Spoiler

  • 0

The music I make.

Simpsons Shizzposting

TAKE IT TO THE ZELDA BREATH OF THE WILD THREAD, IDIOT


#17 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

#18 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

#19 Rize

Rize

    Shizz Gawd

  • Members
  • PipPipPipPipPipPipPipPipPipPip
  • 11,118 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

#20 Daemon9623

Daemon9623

    Shizz Overlord

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 18,936 posts
  • Location:Middle Earth

Posted 28 April 2012 - 10:55 AM

Well that makes me feel a whole lot better! And thanks, everyone, for explaining why, I understand that better now. :) Thanks, Nick, for pointing it out! The point behind the exercise to show which sorting methods are more efficient, so I should be winding up with lower comparison numbers with the selection and insertion methods.

I made a few adjustments to the program to see how the results panned out, but I'm not positive if they're accurate. If someone could run this and tell me where I'm off base I'd be very grateful. :)

Spoiler

  • 0

The music I make.

Simpsons Shizzposting

TAKE IT TO THE ZELDA BREATH OF THE WILD THREAD, IDIOT


#21 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

#22 Daemon9623

Daemon9623

    Shizz Overlord

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 18,936 posts
  • Location:Middle Earth

Posted 28 April 2012 - 12:36 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

I did notice that I missed the curly braces of the inner for loop on the selection sort, but I amended the code and fixed the post with it (must have been while you were responding). I'll make it a smaller array for that one and see how it works out, count the comparisons and whatnot.

edit: cross checked everything against what's in my book and it looks like everything is right! Thanks a lot for your help, guys, it was crucial. :) Now on to the vector portion of the assignment. :P
  • 0

The music I make.

Simpsons Shizzposting

TAKE IT TO THE ZELDA BREATH OF THE WILD THREAD, IDIOT


#23 Rize

Rize

    Shizz Gawd

  • Members
  • PipPipPipPipPipPipPipPipPipPip
  • 11,118 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

#24 auriplane

auriplane

    Shizz Captain

  • Members
  • PipPipPipPipPipPipPip
  • 1,322 posts

Posted 28 April 2012 - 11:33 PM

I tried calculating 5000^5000 on a few online calculators just now for kicks. they report "infinity" as the result :lol:


http://www.wolframal...ut/?i=5000^5000

:-D
  • 3

#25 Nick The Newbie

Nick The Newbie

    Shizz JediMaster

  • Members
  • PipPipPipPipPipPipPipPip
  • 4,439 posts

Posted 29 April 2012 - 06:58 AM

12497500 comparisons? Welcome to O(N^2) algorithms :)

You've discovered exactly why bubble sort is so fucking shitty, hence the reason for this exercise.
  • 2

#26 Rize

Rize

    Shizz Gawd

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

Posted 29 April 2012 - 09:46 AM

I'm going to pick up my old algorithms book and read it cover to cover. I know way less about algorithms than I should considering...
  • 1

#27 XMark

XMark

    Sleeveless

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

Posted 29 April 2012 - 10:12 AM

Bubble sort is the best sorting algorithm for an array that's already sorted :)
  • 1

#28 Daemon9623

Daemon9623

    Shizz Overlord

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 18,936 posts
  • Location:Middle Earth

Posted 29 April 2012 - 10:28 AM

So that half of the assignment is working well, no problem. Now I'm working with string vectors and it's going alright so far, but I've got a few issues.

I can NEVER get it to read an input file correctly! It drvies me nuts because I can't see what I'm doing wrong. What I'm supposed to be doing is having a list of names read from an input file and then store each one in a string vector. I'm also supposed to have the user enter the name of the file and have 3 tries to get it right. My loops work fine and everything functions right, except that when I type in the name of the file it never gets found. As a result, I can't even begin to store the strings in the vector to see if I'm doing it correctly!

Here's my input file code:
Spoiler


The other problem I'm running into is that I need to have the user enter a string, have it stored in a new string vector and then print the string backwards. I know how to do this with a char array and a for loop, but I can't figure it out with a string vector. :huh:
  • 0

The music I make.

Simpsons Shizzposting

TAKE IT TO THE ZELDA BREATH OF THE WILD THREAD, IDIOT


#29 Nick The Newbie

Nick The Newbie

    Shizz JediMaster

  • Members
  • PipPipPipPipPipPipPipPip
  • 4,439 posts

Posted 29 April 2012 - 10:37 AM

could be a path issue? Do you have to enter a fully qualified file name? Are there spaces in the file path?
  • 1

#30 Daemon9623

Daemon9623

    Shizz Overlord

  • Members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 18,936 posts
  • Location:Middle Earth

Posted 29 April 2012 - 10:48 AM

could be a path issue? Do you have to enter a fully qualified file name? Are there spaces in the file path?

No spaces, the path is clearly defined and typed correctly, but I can never get it to read. I'm baffled because I really can't see what I'm doing wrong. :( I've tried it with the full file path and just with just the file name since the program and the file are in the same directory with no luck either way.
  • 0

The music I make.

Simpsons Shizzposting

TAKE IT TO THE ZELDA BREATH OF THE WILD THREAD, IDIOT




Reply to this topic



  


0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users