macOS Sorting multidimensional arrays

[farmerdoug]

I know how to sort a one dimensional array but how do I sort a multidimensional array. The array is a three dimensional array of strings, So I declared array[10][10][10][10]. 10 pages, 10 rows, and 10 columns each holding a string of 10 chars. Now if I find that the string in array[5][10][10] is the greatest, I want to move everything in page zero to a temporary page and move everything on page 5 to page 0 as in a bubble sort. How do I do it? Thanks

 

[angelwatt]

You forgot to mention an important detail, what language?

 

[farmerdoug]

Sorting Arrays.

Same language as all my other posts. :0 C. thanks

 

[lee1210]

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
  char array[10][10][10][10];
  char temp_page[10][10][10];

  int x,y,z,maxpage;
  char maxval[10];

  srand(time(NULL));
  for(x = 0; x < 10; x++) {
    for(y = 0; y < 10; y++) {
      for(z=0;z < 10; z++) {
	sprintf(array[x][y][z],"%d",rand()%1000000000);
	printf("array[%d][%d][%d] : %s\n",x,y,z,array[x][y][z]);
      }
    }
  }

  maxval[0] = '\0';
  maxpage=-1;
  for(x=0;x<10;x++) {
    for(y=0;y<10;y++) {
      for(z=0;z<10;z++) {
        if(strcmp(array[x][y][z],maxval) > 0) {
          strcpy(maxval,array[x][y][z]);
          maxpage=x;
        }
      }
    }
  }
  printf("Max is: %s on page %d\n",maxval,maxpage);

  memcpy(temp_page,array[maxpage],sizeof(char)*1000);
  memcpy(array[maxpage],array[0],sizeof(char)*1000);
  memcpy(array[0],temp_page,sizeof(char)*1000);

  for(x = 0; x < 10; x++) {
    for(y = 0; y < 10; y++) {
      for(z=0;z < 10; z++) {
	printf("array[%d][%d][%d] : %s\n",x,y,z,array[x][y][z]);
      }
    }
  }
  return 0;
}

No warranties, but this seems workable. The juicy bits are the memcpy. Honestly, any bit of 1000 bytes (Assuming 1 byte chars) would work fine as a temporary holding area, but i figured it was easiest to just make the data types match. There are more clever ways if you just use a bunch of pointers (doing a pointer swap would be much quicker), but with the data declared the way you said, this seems to do it.

-Lee

EDIT: This is doing lexicographical comparison of strings i generated with a random number generator... so it's going to look a little funny, but the logic should be sound. I did this with pointers to show an alternative. Doing the swap here is 3 assignment statements, instead of 3 ~3KB copies. On a modern system, copying 9-10KB of data is pretty inconsequential, but it's still worth knowing what it costs to do things a certain way.

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

int main(int argc, char *argv[]) {
  char ***array[10];
  //char temp_page[10][10][10];
  char ***temp_ptr = NULL;

  int x,y,z,maxpage;
  char maxval[10];

  srand(time(NULL));
  for(x = 0; x < 10; x++) {
    array[x] = malloc(sizeof(char**)*10);
    for(y = 0; y < 10; y++) {
      array[x][y] = malloc(sizeof(char*)*10);
      for(z=0;z < 10; z++) {
        array[x][y][z] = malloc(sizeof(char)*10);
	sprintf(array[x][y][z],"%d",rand()%1000000000);
	printf("array[%d][%d][%d] : %s\n",x,y,z,array[x][y][z]);
      }
    }
  }

  maxval[0] = '\0';
  maxpage=-1;
  for(x=0;x<10;x++) {
    for(y=0;y<10;y++) {
      for(z=0;z<10;z++) {
        if(strcmp(array[x][y][z],maxval) > 0) {
          strcpy(maxval,array[x][y][z]);
          maxpage=x;
        }
      }
    }
  }
  printf("Max is: %s on page %d\n",maxval,maxpage);

  temp_ptr = array[maxpage];
  array[maxpage] = array[0];
  array[0] = temp_ptr;

  for(x = 0; x < 10; x++) {
    for(y = 0; y < 10; y++) {
      for(z=0;z < 10; z++) {
	printf("array[%d][%d][%d] : %s\n",x,y,z,array[x][y][z]);
        free(array[x][y][z]);
      }
      free(array[x][y]);
    }
    free(array[x]);
  }
  return 0;
}

This approach does use more total memory.. having 1000 pointers costs 1000*sizeof(void*) + 4 bytes for the extra char ***, whereas the first example uses no extra memory to store array, and uses 1000*sizeof(char) extra bytes for the temp array... so this is costing ~3KB of memory. This could be done even better with one array of 10 pointers, and allocating 1000 bytes and assigning these, then working out the indexes manually. This would use less memory than approach 2, but allow for the faster swapping using pointers.

EDIT 2:

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

char *conv_idx(void *arr,int idxA,int idxB);

int main(int argc, char *argv[]) {
  void *array[10];
  void *temp_ptr = NULL;

  int x,y,z,maxpage;
  char maxval[10];

  srand(time(NULL));
  for(x = 0; x < 10; x++) {
    array[x] = malloc(sizeof(char)*1000);
    for(y = 0; y < 10; y++) {
      for(z=0;z < 10; z++) {
	sprintf(conv_idx(array[x],y,z),"%d",rand()%1000000000);
	printf("array[%d][%d][%d] : %s\n",x,y,z,conv_idx(array[x],y,z));
      }
    }
  }

  maxval[0] = '\0';
  maxpage=-1;
  for(x=0;x<10;x++) {
    for(y=0;y<10;y++) {
      for(z=0;z<10;z++) {
        if(strcmp(conv_idx(array[x],y,z),maxval) > 0) {
          strcpy(maxval,conv_idx(array[x],y,z));
          maxpage=x;
        }
      }
    }
  }
  printf("Max is: %s on page %d\n",maxval,maxpage);

  temp_ptr = array[maxpage];
  array[maxpage] = array[0];
  array[0] = temp_ptr;

  for(x = 0; x < 10; x++) {
    for(y = 0; y < 10; y++) {
      for(z=0;z < 10; z++) {
	printf("array[%d][%d][%d] : %s\n",x,y,z,conv_idx(array[x],y,z));
      }
    }
    free(array[x]);
  }
  return 0;
}

char *conv_idx(void *arr,int idxA,int idxB) { return (char *)arr+idxA*100+idxB*10; }

All of those extra pointers did seem sort of wasteful. Now there're 10 extra pointers instead of 1000, and the swap is still a pointer swap. If you plan to sort within the pages, though, it may be of value to have a pointer allocated for each individual string so you can swap them all up without memcpy'ing around, as was shown in the second example. conv_idx is just convenience. I wrote it originally with all of the pointer calculations "in-line", but it was kind of sloppy. This way it still sort of looks like you're accessing a multidimensional array.

 

[farmerdoug]

WoW.

Thanks. It may take me a day or two to get to it but I'll definitely check it out thoroughly.
Doug

 

[farmerdoug]

I tried your first suggestion. The use of memcpy is neat. I've used it before but never would have thought of it here. After modify some of the names and sizes, I ran the code but got a very strange result:

Max is: Zeus on page 866
Abort trap.

How did Zeus get here?

maxval[0] = '\0';
	maxpage=-1;
	for(i=0;i<1500;i++) {
		for(j=0;j<5;j++) {
			for(k=0;k<45;k++) {
				if(strcmp(averages4[i][j][k],maxval) > 0) {
					strcpy(maxval,averages4[i][j][k]);
					maxpage=i;
				}
			}
		}
	}
	printf("Max is: %s on page %d\n",maxval,maxpage);
	
	memcpy(temp_page,averages4[maxpage],sizeof(char)*2000);
	memcpy(averages4[0],temp_page,sizeof(char)*2000);
	
	for(i = 0; i < 1500; i++) {
		for(j = 0; j < 5; j++) {
			for(k=0;k < 45; k++) {
				printf("averages4[%d][%d][%d] : %s\n",i,j,k,averages4[i][j][k]);
			}
		}
	}

There was also a warning for the first call to memcpy:warning: call to __builtin___memcpy_chk will always overflow destination buffer

I then thought is might be helpful to initialize the array:

for(i=0;i<1500;i++) 
		for(j=0;j<5;j++) 
			for(k=0;k<45;k++)
				strcpy(averages4[i][j][k],'\0');

That only got me into more trouble with a Segmentation fault.

There also seems to be some logic errors but little seems logical this hour of the morning. You only get max page once and put it at the top of the array. I can fix this now that you reminded me of memcopy.

Further work indicates that I don't have to initialize the array.

Hope this is coherent.
thanks.

 

[lee1210]

Can you post all (or at least more) of your code? It's sort of hard to see if the math is right without seeing the declarations, etc.

Also, the way you have things now there's no reason to use temporary memory. You're never copying what's on the 0th page to the "highest" pages previous position. If you don't want to do that, that's fine (though isn't much of a swap), but you can just memcpy right from the desired page to the 0th page if that's the case.

Zeus got there because it was the lexicographically greatest string in your "dictionary".

That's what the strcmp/strcpy business is about.

I feel like the number of bytes in your memcpy can't possibly be right. 45*5=225... 2000 can't be evenly divided by 225. That means there's no length of your fourth dimension that could make 2000 the right number of elements to copy.

-Lee

 

[farmerdoug]

sorting

So, I can't multiply. I also figured out why the maxval = ZEUS. I should be alright from here. I'll let you know if I'm not. Thanks.

 

[farmerdoug]

sorting arrays final code

for(j= (n - 1); j >= 0; j-- )
for(k = 1; k <= j; k++)
if(atoi(averages4[k - 1][3][m]) < atoi(averages4[k][3][m]) )
{
memcpy(temp_page,averages4[k - 1],sizeof(char)*1800);
memcpy( averages4[k - 1],averages4[k],sizeof(char)*1800);
memcpy(averages4[k],temp_page,sizeof(char)*1800);
}

 

[chown33]

I then thought is might be helpful to initialize the array:

for(i=0;i<1500;i++) 
		for(j=0;j<5;j++) 
			for(k=0;k<45;k++)
				strcpy(averages4[i][j][k],'\0');

That only got me into more trouble with a Segmentation fault.

The C expression '\0' is a character constant, not a string. The numeric value of the expression is 0, which is equivalent to NULL, which is not a value that strcpy() will be able to copy from. There may have been a warning associated with this.

 

[farmerdoug]

sorting

thanks.