Solved

# Is this a correct selection sort algorithm?

Posted on 2011-05-13
450 Views
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.

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

}

}
``````
0
Question by:epichero22

LVL 12

Expert Comment

it is a correct bubble sort
0

LVL 11

Author Comment

You sure?  I thought bubble sort stepped through each pair of values and simply swapped them while iterating multiple times through the array.

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

LVL 12

Expert Comment

the first one is better (twice as fast)
in the first version you check half the values (because the first or the last item in the array is at its right position)
0

LVL 37

Assisted Solution

No offense to either of you but...
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.
0

LVL 11

Author Comment

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?

0

LVL 26

Accepted Solution

You can reduce the number of swaps to one per pass through the outer loop (since the item will ultimately only go into one location in the list).  It only requires a single additional variable, so hardly a significant amount of memory.  Something like:

``````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 :)
0

LVL 37

Expert Comment

Yes the solution that dpearson posted is what I was suggesting. Note that it only has no more variables or memory that the first one did. Actually since he just uses the index, it's even faster (if you happen to be sorting things larger than ints, which is common; otherwise it's the same for memory).
0

LVL 11

Author Closing Comment

TY
0

## Featured Post

### Suggested Solutions

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
This is about my first experience with programming Arduino.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…