aknys aknys - 11 days ago 6
C Question

cs50 pset3 sort function

I am having trouble with implementing the sort function on pset3. I have used the GDB and found that my sort function does not sort anything. I am not sure if there is a syntax issue, or if the logic is a bit screwed up.

void sort(int values[], int n)
{
for (int k = 0; k < n; k++)
{
for (int j = 0; j < n; j++)
{
if (values[k] >= values[j])
{
int temp = values[k];
values[k] = values[j];
values[j] = temp;
}
}
}
}

Answer

You are close, but your loops are not quite right - - change:

for (int k = 0; k < n; k++)
{
    for (int j = 0; j < n; j++)
    {

to:

for (int k = 0; k < n - 1; k++)
{
    for (int j = k + 1; j < n; j++)
    {

To understand why you need to make this change, consider that the inner loop (j) must only consider elements above index k. So the outer loop (k) needs to iterate from 0 to n - 2 (one less than the last element), and for each outer loop iteration the inner loop needs to iterate from k + 1 (first element above k) to n - 1 (the last element).

UPDATE: it seems that by some fluke the original code does appear to work correctly, even though it seems that it shouldn't. I'll update the answer later when I've looked at this further. See comments below.


One other minor point -- this test:

        if (values[k] >= values[j])

should really just be:

        if (values[k] > values[j])

It's not incorrect as it stands (the code will still work), but there is no point in swapping elements that are equal, so it's somewhat inefficient as written.

Comments