Search code examples
csortingmultidimensional-arrayquicksortbubble-sort

Sort a two-dimensional array just like a one-dimensional array in C?

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.

Solution

  • 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.