c quicksort not working

Question

Learning C and this is an exercise.

The user is asked to input the dimension of an two-dimensional array. Then the user inputs the values of that array. Finally, the program must be able to sort every line from the lowest to the greatest and print the result.

For instance

input:

2 2
13 11
13 11

Should print:

11 13
11 13

But my program is printing:

11 13
13 11

If in my code I declare a fixed array size, lets say matrix[2][2] and change all the code to that array dimension, the program works great but if I declare matrix[MAX][MAX], since I don know what would be the size of the array, it gives me the output I've posted above.

Is this because I'm not using pointers and memory allocation? (Remember that I'm still learning C).

Here is the code I've done:

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000

/*Print the final two-dimensional array*/
void print( int a[MAX][MAX], int b[])
{
    int i,j;
    for (i=0; i<b[0]; i++)
    {
        for (j=0; j<b[1]; j++)
        {
            printf("%d", a[i][j]);
            if (j < b[1]-1)
            {
                printf(" ");
            }
        }
        printf("\n");
    }
}

/* Sort my array */
int Qsort (int v[MAX][MAX], int li, int ls)
{
    int j;
    if (li < ls)
    {
        j = order(v,li, ls);
        Qsort (v, li, j-1);
        Qsort (v, j+1, ls);
    }
    return v[MAX][MAX];
}


int order(int x[], int li, int ls)
{
    int a, down, up, temp;
    a=x[li]; down=li; up=ls;
    while (down<up)
    {
        while (x[down]<=a && down<ls)
            down ++;
        while (x[up]>a)
            up --;
        if (down < up)
        {
            temp=x[down];
            x[down]=x[up];
            x[up]=temp;
        }
    }
    x[li]=x[up];
    x[up]= a;
    return up;
}

int main()
{
    int i,j,size,jump,jump2;
    int tam[2];
    int matrix[MAX][MAX];

    /*Define rows and columms*/
    i=0;
    while (i<2)
    {
        scanf("%d", &tam[i]);
        i++;
    }

    /*Fill the array with the numbers the user inputs*/
    for (i=0; i<tam[0]; i++)
    {
        for (j=0; j<tam[1]; j++)
        {
            scanf("%d", &matrix[i][j]);
        }
    }

    size = tam[1];
    jump = 1;
    jump2 = 0;

    for(i=0;i<tam[0];i++)
    {
        Qsort (matrix,jump2, jump*size-1);
        jump++;
        jump2 = jump2 + size;

    }

    print (matrix,tam);

    return 0;
}

Thanks,

Favolas

Answer 1

#define MAX 1000
int matrix[MAX][MAX];

/*Fill the array with the numbers the user inputs*/
for (i=0; i<tam[0]; i++)
{
    for (j=0; j<tam[1]; j++)
    {
        scanf("%d", &matrix[i][j]);
    }
}

Given this matrix definition, your 2x2 data ends up in matrix[0][0], matrix[0][1], matrix[1][0] and matrix[1][1]. Nothing startling there, but when regarded as a linear list of cells, the populated cells are:

base_address + 0
base_address + 1
base_address + 1000
base_address + 1001

(where base_address = &matrix[0][0], of course.)

There is no way for your code to examine the latter two cells in the Qsort() code.

There are several conclusions to draw here.

• Learn how to print good diagnostics.
• Print data on entry to a routine. (If you printed the array on entry to Qsort(), you'd see that you don't have the values you thought you should have to work on. This makes sure you know how to access the data accurately.)
• Choose good test data. Do not repeat numbers in your test data (so 11, 12, 13, 14 is a better set of inputs, for example).
• Understand two dimensional arrays and slices of them.

Consider this diagram of a matrix[4][7]:

      0   1   2   3   4   5   6
    +---+---+---+---+---+---+---+
 0  |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+
 1  |   | A | B | C |   |   |   |
    +---+---+---+---+---+---+---+
 2  |   | D | E | F |   |   |   |
    +---+---+---+---+---+---+---+
 3  |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+

If you want to pass the 6 lettered cells to a function as a sub-matrix, you need to pass the address of the cell containing A, you need to know that there are 3 columns and 2 rows, and you also need to know that the width of the whole matrix is 7. Without that 7, you aren't going to find the cells D, E, F. This is a miniature version of your 1000x1000 array, of course.

Your sub-matrix is the top, left-hand corner of the overall matrix, but the same rules apply: you need start address, width and height of sub-matrix, and overall width of the complete matrix to access the correct elements.

(Incidentally, when I first started this explanation, the matrix above was 4x6, not 4x7. Then explaining that the 6 that needs to be passed was not related to the product of 2x3 - the size of the sub-matrix - got tricky, so I changed my 'test case' to avoid the problem - exactly as suggested under 'choose good test data'.)

---

How to fix your code?

There are many ways, depending on what you want to do. The hard way passes the vital matrix-width parameter around. The easier ways probably allocate a 1-D array of cells and then calculate the subscripts manually. However, I'm not sure what you want given the input values 14, 13, 12, 11 (reverse order), the output matrix is supposed to be ... what?

12  11
14  13

This means you need to swap whole rows of your matrix.

Answer 2

It looks like you are sorting the first row over and over. You only want to pass a single column to Qsort so it should be declared:

Qsort(int v[MAX], int li, int ls)

In your main function, simply call Qsort with each successive row:

Qsort(matrix[i], 0, size-1);