Thread: A Sort Algorithm Problem...

  1. #1
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434

    Exclamation A Sort Algorithm Problem...

    Okay, so instead of keeping working on those stupid binary trees =P I figured i'd take a break and look into some sorting algorithms. I made a program which takes 3 algorithms and times how long it takes them to sort (in milliseconds).

    Well there seems to be a problem with one of the algorithms... Sometimes it works, sometimes it doesnt, maybe someone can see what's wrong, here's the function:
    Code:
    void selectSort(vector<int> &v)
    {
    	//Selection Sort Algorithm
    	int temp;
    	for(int i = 0; i<v.size()-1; i++)
    	{
    		temp = v.at(i);
    		for(int j = i+1; j<v.size()-1; j++)
    		{
    			if(v.at(j) < v.at(temp))
    			{
    				temp = j;
    			}
    			swap(v.at(i), v.at(temp));
    		}
    	}
    }
    When it works it sorts them right every time, but sometimes it has a run-time error. It has to do with the vector i think:
    Unhandled exception at 0x7c812a5b in sorting algorithms test 1.exe: Microsoft C++ exception: std:ut_of_range at memory location 0x0013fa08..
    Thanks!
    Last edited by Junior89; 04-10-2007 at 05:47 PM.
    "Anyone can aspire to greatness if they try hard enough."
    - Me

  2. #2
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    temp is being set to some value from the array. So v.at(temp) is not a valid thing to do. You meant, I think, v.at(j) in one instance, and v.at(i) in the other.

  3. #3
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    K i'll double check wikipedia (where i looked up the algorithm) and see if i did'nt implement it right Thanks! But why does it work sometimes though? ha that's what i don't get.

    EDIT-----
    Huh... The code is the same as on wiki, why isn't it working?
    Last edited by Junior89; 04-10-2007 at 06:03 PM.
    "Anyone can aspire to greatness if they try hard enough."
    - Me

  4. #4
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    Ok so i added something which i thought would help... It didn't Same problem as before:
    Code:
    void selectSort(vector<int> &v)
    {
    	//Selection Sort Algorithm
    	int min, minat;
    	for(int i = 0; i<v.size()-1; i++)
    	{
    		min = v.at(i);
    		for(int j = i+1; j<v.size()-1; j++)
    		{
    			if(v.at(j) < v.at(temp))
    			{
    				minat = j;
    				min = v.at(j);
    			}
    			swap(v.at(i), v.at(minat));
    		}
    	}
    }
    "Anyone can aspire to greatness if they try hard enough."
    - Me

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Concerning your most recent code snippet:

    1. What is temp? It is used but has not been declared in selectSort().
    2. Your inner loop should run until the last index as its aim is to find the minimum is the remaining portion of the array.
    3. You should only swap away the current element after having found that minimum.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    One thing that immediately pops out at me is that in selection sort, the swap should not be inside both loops, only the outer one.

  7. #7
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by Junior89 View Post
    Huh... The code is the same as on wiki, why isn't it working?
    Because you did a bad job copying. You added braces at wrong places and changed the limit of the inner loop.
    Kurt

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Microsoft C++ exception:
    Assuming you are using VC++, you should really take a little bit of time and figure out how to use that debugger. It isn't terribly complicated, and it will really help your debugging. You can click "break" to break into the debugger when an exception occurs, then move down the call stack to your code and look at all the variables that are being used, their values, and what line of code is being executed.

  9. #9
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    Thanks for the help! =)
    "Anyone can aspire to greatness if they try hard enough."
    - Me

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. choosing right sort algorithm
    By Micko in forum C++ Programming
    Replies: 15
    Last Post: 05-29-2006, 10:38 AM
  3. Algorithm and sort
    By grepawksed in forum C++ Programming
    Replies: 9
    Last Post: 03-27-2006, 11:23 AM
  4. Selection Sort problem #2
    By Twigstar in forum C++ Programming
    Replies: 7
    Last Post: 07-11-2005, 07:27 PM
  5. Sort algorithm and an ugly error
    By Trauts in forum C++ Programming
    Replies: 7
    Last Post: 02-25-2003, 12:36 PM