1

I want to sort a two-dimensional array like this:

4 2 5
1 3 7
6 9 8

to obtain like this:

1 2 3
4 5 6
7 8 9

using language C.

A couple of options for tackling this problem could include:

  1. Convert the input 2-D array to a 1-D array, and use a standard library function such as sort.

  2. As someone suggested here, I could have a define or a function to access each value using a 1-D index, and employ a insertion-sort or a bubble-sort.

    ARRAY(index) array[(index) / 3][(index) % 3]

I do not like either option because the first one would require a temporary space, and the second one may be slow. My 2-D array would be large in rows and columns. I am also lazy, and wonder if I could employ a standard C library function of qsort. It seems like that I cannot use qsort with 2-D array to get a result of all elements sorted just like 1-D array.

I am given a 2-D array so converting it to a 1-D array is not an option for me.

Thank you for any suggestions.

Sangcheol Choi
  • 841
  • 1
  • 12
  • 19
  • 2
    how do you declare your 2d array? if something like `int a[2][3]`, you can treat it like a 1d array. – gongzhitaao Nov 30 '13 at 01:16
  • Just for the record for who those might not see the discussion below, the array that I want to use is a dynamically allocated "int **a". – Sangcheol Choi Nov 30 '13 at 02:25

2 Answers2

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

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
  int a[3][3] = {{4,2,5}, {1,3,7}, {6,9,8}};

  qsort(a, 9, sizeof(int), compare);

  int i, j;
  for (i = 0; i < 3; ++i) {
    for (j = 0; j < 3; ++j)
      printf("%d ", a[i][j]);
    printf("\n");
  }
  return 0;
}

If you declare your array like int **a. then maybe you could use the following technique, which requires some extra memory:

int *a_mem = (int *)malloc(9 * sizeof(int));
int **a = (int **)malloc(3 * sizeof(int *));
for (i = 0; i < 3; ++i)
  a[i] = &a_mem[i * 3];

qsort(a_mem, 9, sizeof(int), compare);
gongzhitaao
  • 6,566
  • 3
  • 36
  • 44
  • Thanks! That is so a simple and concise answer. – Sangcheol Choi Nov 30 '13 at 01:52
  • Just a comment: If "a" the array was created as "int **a", then qsort's first argument can be changed to *a. – Sangcheol Choi Nov 30 '13 at 02:05
  • @SangcheolChoi Hi, if you declare your array as `int **a`, then you may not use this. Because the assumption behind this is the memory is continuous :) – gongzhitaao Nov 30 '13 at 02:06
  • @SangcheolChoi Or, you could use some extra memory to makeup for this. I used it sometime. See the updated snippet :) – gongzhitaao Nov 30 '13 at 02:11
  • I thought that way! So, a testing code that I made might have worked just at random because memory happened to be allocated contiguously. Then, should I resort to a custom sorting function as CurlyCorvus suggested above? – Sangcheol Choi Nov 30 '13 at 02:11
  • @SangcheolChoi Besides the way in my post or the way CurlyCorvus suggested, I couldn't think of other ways. :) – gongzhitaao Nov 30 '13 at 02:13
  • Having a temporary 1-D array is not my option as I mentioned in my question because the 2-D array itself is large and my memory usage is limited. Thank you, gongzhitaao, for your thought, though! – Sangcheol Choi Nov 30 '13 at 02:13
  • Thank you, gongzhitaao! I was surprised by my toy example where "int **a" worked. It seems like that that was just a random result. – Sangcheol Choi Nov 30 '13 at 02:15
2

As gongzhitaao mentioned in his comment, if the array is defined as int `a[n][m]`, then it is defined as a continuous block in the memory, ergo it can be accessed as if it is a one dimensional array by providing a pointer to the first element and providing n*m as the array length. You can find much more detailed explanations about how arrays work in c in the questions http://stackoverflow.com/questions/4810664/how-do-i-use-arrays-in-c/4810668 and http://stackoverflow.com/questions/7949589/2d-array-vs-array-of-arrays.

If that is not the case, however, using an access function is the best option for 2 reasons:
1. That is the most intuitive to do it. If you define the array as int* a[n] then it is possible to have n pointers to m non consecutive arrays. This means that as far algorithms go you have to way to tell what element will come next (for sorting), unless you define a function for it.
2. It is not slow at all. The only change in whatever sorting algorithm you choose is replacing each one dimensional array access (a[i]) with your new access function (getArrayElement(a,i,j)). The function itself is so small it might even get inlined during compilation, so the only overhead is the calculation, which is two extra arithmetic functions per access. Since does not change the O complexity (see Wikipedia) of the algorithm, meaning it will not contribute much to slowing down your program.

SilverCorvus
  • 2,956
  • 1
  • 15
  • 26