Solved

Posted on 2011-05-13

It differs from the example in the book, but it appears to work. The selection sort is supposed to start with the first element in an array and compare it to every element after that. If it finds a number that's out of order, it swaps. Let me know what you think:

nums[] is the array of number, S is the size of the array.

nums[] is the array of number, S is the size of the array.

```
void selectionSort(int nums[], const int S)
{
int temp;
for (int i = 0; i < S; i++)
{
for (int j = i + 1; j < S; j++)
{
if (nums[j] < nums[i])
{
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
}
```

8 Comments

Here is my code for a bubble sort:

```
void bubbleSort(int nums[], const int S)
{
int temp;
bool flag = true;
do
{
flag = true;
for (int i = 0; i < S - 1; i++)
{
if (nums[i] < nums[i + 1])
{
flag = false;
temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
}
}
}while (flag == false);
}
```

in the first version you check half the values (because the first or the last item in the array is at its right position)

The first one is not bubble sort.

The first one is a bad implementation of selection sort.

It is selection sort because you are iterating through to find the lowest and swapping it with the first element. The reason the first one is bad is because you swap every time you find a better one. This introduces lots of extra calls to the = operator since swapping calls in twice. The standard method is a little better.

The second one is a bad implementation of bubble sort for the reason enachemc mentioned.

Every time you run the inner for loop, you are guanranteed that the last element is in the right place. So the outer loop should be a for loop like for(int i = S, i > 0, --i) and the inner one would use i as the upper limit.

The reason the first one is bad is because you swap every time you find a better one. This introduces lots of extra calls to the = operator since swapping calls in twice.

So I'm guessing that the better way to go about doing it would be to assign lower values to a variable as you go. But wouldn't that also require more memory? What is best to optimize?

```
for (int i = 0; i < S; i++)
{
int elementToMove= i ;
for (int j = i + 1; j < S; j++)
{
if (nums[j] < nums[elementToMove])
{
elementToMove = j ;
}
}
// Now do the swap of nums[elementToMove] and nums[i]
// NOTE: This is not inside the inner loop so you'll do O(n) swaps not O(n^2)
....
}
```

The real question though is why would you ever use selection sort? It's just ugly.

Bubble sort is actually quite nice if you want to use an O(n^2) sort (rather than an optimal O(n log-n) sort like quick sort) because it has one very useful special feature. If you give it an already sorted list it's O(n) (when written correctly). And in the real world, many times we want to sort a list that's already mostly sorted.

Doug

P.S. If you have no idea what all this O(n) stuff is I'm talking about suffice to say O(n) is faster than O(n log-n) which is faster than O(n^2). In the same way that 10 seconds is faster than 100 hours :)

Title | # Comments | Views | Activity |
---|---|---|---|

PHP Loan Calculation formula help. | 8 | 59 | |

Paint/Redraw window while dragging | 16 | 47 | |

Permutation and Combination | 9 | 26 | |

cmd.exe will not close when running .bat file to perform FTP upload | 18 | 50 |

This is about my first experience with programming Arduino.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**15** Experts available now in Live!