# Selection sorting algorithm

Printable View

• 04-06-2004
neandrake
Selection sorting algorithm
Selection sort scans an array of ints to find the smallest, then replaces the first element with the smallest. When(if) that happens, the routine continues again but this time excluding the first element(which is now the smallest), and so on.

When I run the program, I get this:
Code:

`{ 3 4 6 5 8 8 65 13 66 748 }`
the code:
Code:

```#include <iostream> using namespace std; const int MAX_ELEMENTS = 10; void selsort(int [], int); int main() {     int unsorted[MAX_ELEMENTS] = {5,3,748,6,8,65,8,66,4,13};                                 //3,4,5,6,8,8,13,65,66,748     selsort(unsorted, 0);     cout << "{ ";     for (int i=0; i<MAX_ELEMENTS; i++)     {         cout << unsorted[i] << " ";     }     cout << "}" << endl;     cin >> unsorted[0];     return 0; } void selsort(int array[], int loc) {     if (loc == (MAX_ELEMENTS-1))         return;     int tmp = 0;     for (int i=loc; i<MAX_ELEMENTS; i++)     {         if (array[i] < array[loc])         {             tmp = array[loc];             array[loc] = array[i];             array[i] = tmp;             selsort(array, loc + 1);         }     }     //if (locsmall == 0)     //    return; }```
• 04-06-2004
jlou
Why did you change it? It was right except for one small thing (I pointed to the line with the problem as a hint in the other thread).
• 04-06-2004
neandrake
There was no need for the locsmall, so it doesn't matter now, I just took it out. What is the problem with locsmall being set to 0?
• 04-06-2004
jlou
Since you initially set small to the value at array[loc], then you should have initially set locsmall to loc. When I did that with your original code, the data was sorted correctly.

The first algorithm was: Look at all values after the passed in location and find the smallest remaining value. Then, swap the current location with the smallest remaining that was just found. Recurse on the next location. I don't know if that's selection sort, but it works.

The new algorithm is: For each element after the current location, if that element is smaller, immediately swap it and then recursively sort the rest of the array. The problem with that is that after two positions have been compared, its possible that different values can get swapped into the positions that are no longer in the correct order (I believe that is what is happening here). Here are the swaps I get for your new code:

5, 3, 748, 6, 8, 65, 8, 66, 4, 13
3, 5, 748, 6, 8, 65, 8, 66, 4, 13
3, 4, 748, 6, 8, 65, 8, 66, 5, 13
3, 4, 6, 748, 8, 65, 8, 66, 5, 13
3, 4, 6, 8, 748, 65, 8, 66, 5, 13
3, 4, 6, 8, 65, 748, 8, 66, 5, 13
3, 4, 6, 8, 65, 8, 748, 66, 5, 13
3, 4, 6, 8, 65, 8, 66, 748, 5, 13
3, 4, 6, 8, 65, 8, 66, 5, 748, 13
3, 4, 6, 8, 65, 8, 66, 5, 13, 748
3, 4, 6, 8, 65, 8, 13, 5, 66, 748
3, 4, 6, 8, 65, 5, 13, 8, 66, 748
3, 4, 6, 8, 65, 5, 8, 13, 66, 748
3, 4, 6, 8, 8, 5, 65, 13, 66, 748
3, 4, 6, 5, 8, 8, 65, 13, 66, 748

Notice how in the fourth row, the third spot (6) is now less than the fourth spot (748). Later, 5 gets moved into the fourth spot, but the algorithm has already compared the third and fourth spots and so it assumes they are still in order, leaving the 5 after the 6 in the array.