cs50 pset3 sort function

Question

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 1

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) need only compare elements above index k with the current element at 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).

NOTE: by pure chance it seems that the original code does appear to work correctly, even though it appears at first glance that it shouldn't. I have tested it with various edge cases and even though it performs many redundant swaps, the final result always seems to be sorted (suprisingly though the output is in descending order whereas the fixed code generates results in ascending order, as expected). Credit to Jonathan Leffler for spotting this - see his answer and demo program.

---

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.

Answer 2

I took your code and converted into a complete program. It's larger than an MCVE because it has support code for shuffling arrays, and for printing results, as well as a main() that exercises these, of course.

#include <stdio.h>
#include <stdlib.h>

static int rand_int(int n)
{
    int limit = RAND_MAX - RAND_MAX % n;
    int rnd;

    while ((rnd = rand()) >= limit)
        ;
    return rnd % n;
}

static void shuffle(int *array, int n)
{
    for (int i = n - 1; i > 0; i--)
    {
        int j = rand_int(i + 1);
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }
}

static void print_array(int n, int a[n])
{
    for (int i = 0; i < n; i++)
        printf(" %d", a[i]);
    putchar('\n');
}

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

int main(int argc, char **argv)
{
    if (argc > 1)
    {
        long l = strtol(argv[1], 0, 0);
        unsigned u = (unsigned)l;
        printf("Seed: %u\n", u);
        srand(u);
    }

    int data3[3] = { 3, 1, 2 };
    print_array(3, data3);
    sort(data3, 3);
    print_array(3, data3);

    int data5[5] = { 0, 2, 6, 1, 5, };
    for (int i = 0; i < 5; i++)
    {
        shuffle(data5, 5);
        print_array(5, data5);
        sort(data5, 5);
        print_array(5, data5);
    }

    int data9[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    for (int i = 0; i < 9; i++)
    {
        shuffle(data9, 9);
        print_array(9, data9);
        sort(data9, 9);
        print_array(9, data9);
    }

    return 0;
}

The shuffle code implements a Fisher-Yates shuffle, and is based on code from an answer by Roland Illig. If invoked without a seed argument, it generates the same output each time.

Code compiled and tested on macOS Sierra 10.12.1 with GCC 6.2.0.

An example output:

Seed: 123456789
 3 1 2
 3 2 1
 6 0 1 5 2
 6 5 2 1 0
 0 6 1 2 5
 6 5 2 1 0
 0 1 2 6 5
 6 5 2 1 0
 5 0 6 1 2
 6 5 2 1 0
 1 6 5 2 0
 6 5 2 1 0
 0 4 8 3 7 5 1 6 2
 8 7 6 5 4 3 2 1 0
 7 4 0 5 6 8 3 2 1
 8 7 6 5 4 3 2 1 0
 1 2 7 5 0 8 3 6 4
 8 7 6 5 4 3 2 1 0
 3 8 7 5 2 1 0 6 4
 8 7 6 5 4 3 2 1 0
 1 4 2 6 3 0 7 5 8
 8 7 6 5 4 3 2 1 0
 2 3 7 4 8 0 5 6 1
 8 7 6 5 4 3 2 1 0
 3 4 5 8 6 2 0 7 1
 8 7 6 5 4 3 2 1 0
 3 6 7 4 8 2 5 1 0
 8 7 6 5 4 3 2 1 0
 0 8 7 3 4 6 5 1 2
 8 7 6 5 4 3 2 1 0

This shows the data being sorted in descending order every time, despite different randomized inputs.