Sorting Arrays Help

[Anup Patel]

I have 2 questions to help me with my homework, it would be great if you guys could point me in the right direction.

1. I have a character array with strings for example
"media room 20"
"main room 15"
Whats the best approach to sorting this string array by the number at the end?

2. I have a multi dimensional array a[5][23][10]
How can i sort this by retaining all of the data in the correct spots with each other
For example
[0][1][9] = 10
[0][2][9] = 20
[1][1][9] = 13
[2][1][9] = 25
if i want to sort this by for all of the values, what can i do?

Thanks for all your help guys!

[Adak]

1) Make the data into a struct, then sort according to the key struct member you want to sort by. Everything in the struct gets moved while it's being sorted.

2) Use parallel arrays. One char array, (string[][]), and one int array. Sort the int array as per normal. BUT whenever you make a swap, you need to swap the strings in the matching string index, at the same time.

So it's a 2 part "dance", but the partners string[i] and data[i] are always together, on the same index (the i).

[laserlight]

Whats the best approach to sorting this string array by the number at the end?

"Best" depends on your exact requirements, but one approach is to parse each string to extract the number, then store the string (or a pointer thereof) and this number into a struct object. This way, you can use qsort to sort an array of these struct objects.

How can i sort this by retaining all of the data in the correct spots with each other

You need to be clear on what you mean by that. Also, it may be easier to work out your ideas with a 2D array first.

[Nominal Animal]

1. I have a character array with strings for example
"media room 20"
"main room 15"
Whats the best approach to sorting this string array by the number at the end?

Like Adak and laserlight said, it depends.

Personally, I'd create a structure that can hold the key -- here, the numeric value at the end --, and a pointer to the actual string; just like Adak's first suggestion. Then I'd write a function that can compare two such structures the same way strcmp() compares strings:

struct element {
    double key;
    char  *line;
};

/* Return -1 if ptr1 < ptr2, +1 if ptr1 > ptr2, and 0 if they are equal.
*/
static compare_elements(const void *const ptr1, const void *const ptr2)
{
    const double d = ((const struct element *)ptr1)->key - ((const struct element *)ptr2)->key;

    if (d > 0.0)
        return +1;
    else
    if (d < 0.0)
        return -1;
    else
        return  0;
}

If you then create an array of those structures, populate it with the pointers to each line, and parse the number to the key field at end, you can sort this new array using

qsort(array, elements, sizeof (struct element), compare_elements);

That will not modify the original string array, only the new array. On the other hand, the new array will have the pointer to each full string in the desired order, so you'd just use this new array instead of the string array.

While it does not really matter what each structure contains, I recommend against storing the strings themselves within the structure. If you do that, qsort() has to move lots of memory around, slowing it down. It is better to just use pointers to the strings instead, if they are to be sorted.

2. I have a multi dimensional array a[5][23][10]
How can i sort this by retaining all of the data in the correct spots with each other

What might the correct spots be? No, really; that is the question.

Sorting items means placing them in order, along one axis. When you have say

   ║ A │ B │ C │ 
 ══╬═══╪═══╪═══╪══
 1 ║.1 │.2 │.5 │ 
 ──╫───┼───┼───┼──
 2 ║.4 │.6 │.7 │ 
 ──╫───┼───┼───┼──
 3 ║.8 │.9 │.3 │ 
 ──╫───┼───┼───┼──
   ║   │   │   │

and you wish to sort them in ascending order, you have lots of possibilities:

1. Sort rows in ascending order by column A
2. Sort rows in ascending order by column B
3. Sort rows in ascending order by column C
4. Sort columns in ascending order by row 1
5. Sort columns in ascending order by row 2
6. Sort columns in ascending order by row 3
7. Sort all nine values in ascending order

For example, for the option 2 the result is the same as the input. For option 6, the result is

   ║ C │ A │ B │ 
 ══╬═══╪═══╪═══╪══
 1 ║.5 │.1 │.2 │ 
 ──╫───┼───┼───┼──
 2 ║.7 │.4 │.6 │ 
 ──╫───┼───┼───┼──
 3 ║.3 │.8 │.9 │ 
 ──╫───┼───┼───┼──
   ║   │   │   │

For option 7, the result is not a table but just a list:

.1 .2 .3 .4 .5 .6 .7 .8 .9

Your array has three dimensions, but otherwise the situation is just the same.

So, before anything else, you must be able to clearly explain what kind of sort operation you need. Show a complete example, with both input and results, for example. Use a smaller array, say 3x3x3 (27 values).

[Adak]

This is a parallel array sorter example, for comparison. I added code to this, and haven't compiled it. Let me know if you have any errors or warnings.

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

    #define SIZE 20

    void sort(char a[][SIZE], int *, int);
    void swap(char a[][SIZE], int *, int, int);

    int main(void) {
    int i,n,b[4]={40,30,50,70};
    char a[4][20]={{"Adam"},{"Abigail"},{"Abby"},{"Abe"}};
  
    n=SIZE; 
    printf("\nBefore sorting\n a: b:\n\n");
    for(i=0;i<n;i++)
       printf("%s %3d\n",a[i],b[i]);

    sort(a,b,n,0); //sort with a as the key
    printf("\nAfter sorting, A is the key:\n a: b:\n\n");
    for(i=0;i<n;i++)
       printf("%s %3d\n",a[i],b[i]);
   
    //now sort it with b[] as the key
    sort(a,b,n,1);
    for(i=0;i<n;i++) {
       printf("%s %3d\n",a[i],b[i]);
    }
    printf("\n");
    return 0;
}
//a substitution sort
void sort(char a[][SIZE], int *b, int n, int type) {
    int i,j;

    if(!type) {
       for(i = 0;i < n-1; i++)  {
          for(j = i+1;j<n;j++)   {
             if(strcmp(a[i],a[j])>0) {
                swap(a,b,i,j);
             }
          }
       }
    }
    else {
       for(i=0;i<n-1;i++) {
          for(j=i+1;j<n;j++) {
             if(b[i] > b[j]) {
                swap(a,b,i,j);
             }
          }
       }
    }
}
//swaps both arrays, so the data stays with the right name
void swap(char a[][3], int *b, int i, int j) {
    int temp;
    char ctemp[SIZE];

    strcpy(ctemp,a[i]);
    strcpy(a[i], a[j]);
    strcpy(a[j], ctemp);

    //swap the b array
    temp = b[i];
    b[i] = b[j];
    b[j]= temp;
 }

Parallel arrays are taught before structs, but structs are far more versatile to work with. With only two items, either parallel arrays or structs, are good. If you had 3 or more data entries per record, structs would definitely be what you'd want to use.