Link to home
Start Free TrialLog in
Avatar of epichero22
epichero22Flag for United States of America

asked on

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

Avatar of enachemc
enachemc
Flag of Afghanistan image

it is a correct bubble sort
Avatar of epichero22

ASKER

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

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)
SOLUTION
Avatar of TommySzalapski
TommySzalapski
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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?




ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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).
TY