Computer Science Canada

Sort 2D array
Author:  javanoob [ Thu Jan 22, 2009 12:07 pm ]
Post subject:  Sort 2D array
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.
Author:  DemonWasp [ Thu Jan 22, 2009 12:22 pm ]
Post subject:  RE:Sort 2D array
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).
Author:  javanoob [ Thu Jan 22, 2009 12:50 pm ]
Post subject:  Re: Sort 2D array
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?
Author:  DemonWasp [ Thu Jan 22, 2009 2:11 pm ]
Post subject:  RE:Sort 2D array
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.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy