Sort 2D array

[javanoob]

I've been given an assignment that requires me to (among other things) sort a 2d array of integers using bubble sort. I know how I would sort a single dimension of integers but I'm a little lost on how to extrapolate that to 2d.

code:

#include <stdio.h> #include <stdlib.h>         #define M 10 #define N 5         void initializeArray2D(int array[][N], int r, int c); void printArray2D(const int array[][N], int r, int c); void populateRandomValues2D(int array[][N], int r, int c); void sort2D(int array[][N], int r, int c); void linearSearch2D(int array[][N], int r, int c, int num);         int main() {         int array[M][N], num;                   initializeArray2D(array, M, N);         printArray2D(array, M, N);         populateRandomValues2D(array, M, N);         printArray2D(array, M, N);         sort2D(array, M, N);         printArray2D(array, M, N);         printf("Number to find: ");         scanf("%d", &num);         linearSearch2D(array, M, N, num);                 return 0; } void initializeArray2D(int array[][N], int r, int c) {         int i;         int j;           for (i=0; i<r; i++)          {                 for (j=0; j<c; j++)                 {                         array[i][j] = 0;                 }         } } void printArray2D(const int array[][N], int r, int c) {         for (int r=0; r<M; r++)         {                 for(int c=0; c<N; c++)                 {                         printf("%8d", array[r][c]);                 }                 printf("\n");         }         printf("\n\n"); }           void populateRandomValues2D(int array[][N], int r, int c) {         for (int r=0; r<M; r++)         {                 for(int c=0; c<N; c++)                 {                         array[r][c] = (1+(rand()%100));                 }         } }           void sort2D(int array[][N], int r, int c) {                         }                 void linearSearch2D(int array[][N], int r, int c, int num) {   }

So obviously the 2d bubble sort will go in the function sort2D, and the linear search I haven't coded yet...but that shouldn't be a problem.

My teacher said something about treating the array as if it were only a single dimension, but I'm still not exactly sure how that would work?? Any help is appreciated.

[DemonWasp]

The key here is that a 2-dimensional array isn't actually 2-dimensional in memory. Being able to address it as if it were a 2d array is just syntactic "sugar". In reality, the array is stored as a 1d array (this is by necessity; memory is actually essentially just one really big 1d array with elements 0..4 billion (for a machine with 4GB RAM)).

How is it stored? The array is stored in (as I recall) row-major order. This means that the array first contains the first row, then the second row, then the third row, etc, all stuck together.

code:

2D Array Representation (most of your code): (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) 1D Array Representation (RAM): (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)

What this means is that you can use some C silliness to treat your (supposedly) 2D array as a 1D array. You can then sort the 1D array.

If you think about it for a few minutes, I'm sure you can come up with a relatively simple way of translating the 1D coordinate and the 2D coordinates back and forth trivially; all you'll need to know is the length of each row (which appears to be N, from a glance at your code).

[javanoob]

OK...is that what this would be for then?

i = x * M + y
x = i / M
y = i % M

I remember him briefly talking about this...but I can't remember exactly what each value would be. M is obviously the number of rows. Would i be the element I'm trying to find, and x and y be the row and column number?

[DemonWasp]

You're pretty close. Here's how you logic it out, using our sample array:

code:

2D:   0 1 2 3 .... X 0 A B C D 1 E F G H 2 I J K L . . Y 1D: 0 1 2 3 4 5 6 7 8 9 . . . A B C D E F G H I J K L

If we want something from the first row (something, 0), then the value for i is simple (it's "something").

If we want something from the second row (something, 1), then the value for i is ( 1 row worth of columns ) + "something".

In fact, i = y * (columns) + x in general. This is because there are (y rows) * (#columns) entries before that row begins, and x more on that row.

To go the other way, we can use division similar to what you've got, but not quite the same.

y = i / (#columns)
x = i % (#columns)

All you'd need to do to use this is code your sort to use a method called swap ( int pos1, int pos 2 ) which takes positions for a 1d array and converts them into positions for the 2d array. Your sort method can pretend it's dealing with a 1D array - in fact, it's identical; the only thing that's

I should mention that there are ways of making C do that work for you, but they require a fairly advanced knowledge of exactly how C works.