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:

Quote:

---

Unhandled exception at 0x7c812a5b in sorting algorithms test 1.exe: Microsoft C++ exception: std::out_of_range at memory location 0x0013fa08..

---

Thanks!

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.

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?

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));
                }
        }
}

---

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.

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.

Quote:

---

Originally Posted by Junior89

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

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

Thanks for the help! =)