epichero22
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.
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;
}
}
}
}
it is a correct bubble sort
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:
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);
}
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)
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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).
ASKER
TY