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.

Improve this question
2
  • 2
    how do you declare your 2d array? if something like int a[2][3], you can treat it like a 1d array. Commented Nov 30, 2013 at 1: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". Commented Nov 30, 2013 at 2:25

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thank you very much for your answer. I think that I would have to employ a custom sorting function as you suggest.
Thank you for the two links about arrays.
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);
Improve this answer

8 Comments

Thanks! That is so a simple and concise answer.
Just a comment: If "a" the array was created as "int **a", then qsort's first argument can be changed to *a.
@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 :)
@SangcheolChoi Or, you could use some extra memory to makeup for this. I used it sometime. See the updated snippet :)
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?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.