• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 500
  • Last Modified:

Is this a correct selection sort algorithm?

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

	}

}

Open in new window

0
epichero22
Asked:
epichero22
  • 3
  • 2
  • 2
  • +1
2 Solutions
 
enachemcCommented:
it is a correct bubble sort
0
 
epichero22Author Commented:
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);
}

Open in new window

0
 
enachemcCommented:
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
TommySzalapskiCommented:
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
 
epichero22Author Commented:
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
 
dpearsonCommented:
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)
                 ....
}

Open in new window


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
 
TommySzalapskiCommented:
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
 
epichero22Author Commented:
TY
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 3
  • 2
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now