Is it possible to sort in ascending order, a 2D array in C? If so, how?

Question

Part of my assignment is to sort a 2D array into ascending order, and I cannot figure out how to do it for the life of me.

What I have so far:

int Sort2DArray(int A[][COL], unsigned int rowsize, unsigned int colsize)
{
 int i, j, k, temp;
 for (i=0; i<rowsize-1; i++){
     for (k=0; k<colsize; k++){
        for (j=0; j<rowsize-1; j++){
            do  {
             temp = A[k][j];
             A[k][j] = A[k][j+1];
             A[k][j+1] = temp;
            } while (A[k][j]>A[k][j+1]);
        }
     }
 }
}

This will take an array this and return:

3 2 1               1 2 3
5 8 7    ---->>>    5 7 8
4 9 3               3 4 9

However, I need it to return:

1 2 3
4 5 6
7 8 9

So, is there any way you guys can help me? Thanks!

EDIT:

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

#define COL 20
#define ROW 20

void PopulateArray2DUnique (int [][COL], unsigned int, unsigned int, int, int);

void DisplayArray2D(int [][COL], unsigned int, unsigned int);

int FindLargest(int [][COL], unsigned int, unsigned int);

int FindColSum(int [][COL], unsigned int, unsigned int, unsigned int);

int Sort2DArray(int [][COL], unsigned int, unsigned int);

int main()
{
 int A[ROW][COL];
 int min=1, max=99;
 unsigned int rowsize, colsize, col_to_sum;

 printf ("Input your desired row and column size: \n");
 scanf ("%u%u", &colsize, &rowsize);

 PopulateArray2DUnique(A, rowsize, colsize, min, max);
 DisplayArray2D(A, rowsize, colsize);
 FindLargest(A, rowsize, colsize);

    printf ("Which column would you like to find sum of?\n");
    scanf ("%d", &col_to_sum);

 FindColSum(A, rowsize, colsize, col_to_sum);
 Sort2DArray(A, rowsize, colsize);
 DisplayArray2D(A, rowsize, colsize);

 return 0;
}

Answer 1

Is it possible?

Yes, it's possible. The most important thing to understand is that your sort routine, and all of the basic sort routines you see in examples, generally sort a 1D array.[1] The same routine can be used to sequentially sort a 2D array as you are attempting to do, but you have to recognize you want to pass your 2D array to the sort function as a pointer-to-type (simple 1D array, e.g. 'int *'), rather than as a pointer-to-array of X elements (your 2D array, e.g. 'int (*)[NCOLS]')

The key to passing the array is to simply pass the address to the first element in your array. Regardless of whether you declared it as a 1D or 2D array (1) that is the address where the values begin in memory; and (2) all array values are sequential. Meaning that you can address every value in a 1D or 2D array by start_address + offset.

Take for example your simple bubble-sort routine:

void bubblesort (int *a, size_t n)
{
    size_t i, j;
    int temp;

    for (i = 0; i < n; i++) {
        for (j = 0; j < (n-1); j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
    }
}

If you had declared a 2D array (e.g. int array[][NCOL];, not pointer-to-pointer-to-type int **array;) that you wished to sequentially sort, you could call your sort routine by simply passing the start address as follows:

    bubblesort (*array, nelem);

or

    bubblesort (&array[0][0], nelem);

(both are equivalent, with 'nelem' being the total number of elements)

If you attempt to declare your sort function by passing a pointer to array (e.g. bubblesort (int (*array)[NCOL], size_t n); you will run difficulty immediately attempting to loop over the indexes because using the traditional nested loop layout, there is no easy way to compare array[i][j] with array[i+1][0], etc..

The following is a short example putting it all together. Look it over and let me know if you have questions:

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

#define NCOL 3

void bubblesort (int *a, size_t n);

int main ()
{
    int array[][NCOL] = {{3,2,1},
                         {5,8,7},
                         {4,9,3}};
    int i, j, nrows, nelem;

    nrows = sizeof array/sizeof *array;
    nelem = sizeof array/sizeof **array;

    printf ("\noriginal:\n\n");
    for (i = 0; i < nrows; i++) {
        for (j = 0; j < NCOL; j++)
            printf (" %2d", array[i][j]);
        putchar ('\n');
    }

    bubblesort (*array, nelem);

    printf ("\nsorted:\n\n");
    for (i = 0; i < nrows; i++) {
        for (j = 0; j < NCOL; j++)
            printf (" %2d", array[i][j]);
        putchar ('\n');
    }

    return 0;
}

void bubblesort (int *a, size_t n)
{
    size_t i, j;
    int temp;

    for (i = 0; i < n; i++) {
        for (j = 0; j < (n-1); j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
    }
}

Output

$ ./bin/qsort_2d_linear

original:

  3  2  1
  5  8  7
  4  9  3

sorted:

  1  2  3
  3  4  5
  7  8  9

Note: you can do the same thing with qsort rather easily with the standard integer compare function and calling qsort (array, nelem, sizeof **array, icompare);

footnote[1]: all arrays in C are 1D arrays, the 2D array is simply addressed in a way to allow 2D indexing. It is still a sequential block of 'type' values in memory.)

Answer 2

I'm not sure if I have the best method here, however what I would do, is store each value from the array into one large 1D array, sort that and then assign them to the 2D array.

int Sort2DArray(int A[][COL], unsigned int rowsize, unsigned int colsize)
{
    int arraySize = rowsize * colsize;
    int sortingArray[arraySize];
    int i = 0, row, col, temp, prevPos;

    //Fills the sortingArray with all the values in the 2D array
    for (col = 0; col < colsize; ++col) {
        for (row = 0; row < rowsize; ++row) {
            sortingArray[i] = A[row][col];
            ++i;
        }
    }

    //Sorts the 1D array (Insertion Sort)
    for (i = 1; i < arraySize; ++i)
    {
        temp = sortingArray[i];
        prevPos = i - 1;
        while (j >= 0 && sortingArray[prevPos] > temp)
        {
            sortingArray[prevPos+1] = sortingArray[prevPos];
            prevPos = prevPos - 1;
        }
        sortingArray[prevPos + 1] = temp;
    }

    //Writes data back into 2D array
    i = 0;
    for (row = 0; row < rowsize; ++row) {
        for (col = 0; col < colsize; ++col) {
            A[row][col] = sortingArray[i];
            ++i;
        }
    }
}

I hope I didn't get too confusing with all those dimensions, but you get the idea. If you spot anything incorrect, let me know.

Answer 3

It smells like homework to me, thus, I will only help you a little, and leave the rest to yourself.

When I was very new to C, and my first programming language, I had solved a lot of problems, and one of them was this.

The code I am pasting here is taken from here, a website, which I used to use a lot.

It is up to you to understand the algorithm, and program, and use it in your program.

#include<stdio.h>

int main( )
{

    int a[][6]={
                {25,64,96,32,78,27},      //Desired solution : {25,27,32,64,78,96},
                {50,12,69,78,32,92}       //                   {50,92,78,12,32,69}
                };
     int i, j, k, temp, temp1 ;

    //Bubble sorting is applieed on one first row while the other row is swapped

     for(j=1;j<6;j++)
     {
          for(i=0; i<5; i++)
          {
                if(a[0][i]>a[0][i+1])
                {
                    temp=a[0][i];
                    a[0][i]=a[0][i+1];
                    a[0][i+1]=temp;

                    temp1 = a[1][i];
                    a[1][i] = a[1][i+1];
                    a[1][i+1]=temp1;
                }
          }
     }

     printf ( "\n\nArray after sorting:\n") ;
     for ( i = 0 ; i <2; i++ )
     {
        for(j=0; j<6; j++)
        {
            printf ( "%d\t", a[i][j] ) ;        //printing sorted array
        }
        printf("\n");
     }
 }

It is a bit different from the code on the site, as I used to always used to work in Ubuntu, and linux never had conio.h. Also, if you are angry for me only providing the code used everywhere, and not doing all your work, keep in mind that homework assignments are for making the student think, and if I spoon-feed you, the purpose will be lost.

NOTE: Always post your full code which can be compiled successfully, as the code you have posted does not compile, as you have not declared all your functions. Thus, it is very difficult to understand you code.

Also, do not try to fool us, as the input you have mentioned does not have a 6, and you want a 6 also to be returned so actually even you have not compiled your code.