Sorting of an array

Question

I am programming in C. I have an array of structures. I need to print the array in sorted order based on an element of the structure. The main problem where I am stuck is I do not want to modify the original array.

For example: My array is proctab[10]. This is the array of structure named pentry.

struct pentry
{
    int a;
    int b;
    char c;
}

I need to print as follows:

a = 1, b = 2, c = a
a = 2, b = 1, c = d
a = 3, b = 0, c = e
a = 4, b = 1, c = a
a = 4, b = 2, c = a

and so on.. i.e. the result is sorted on a. but if a has same value for two structures in the array, the array should be sorted on b as well.

I want the original array proctab to remain intact.

Is there any way to do this?

If it helps, I know in Java you'd just make the object implement `Comparable` and implement `compareTo` - I'm sure there's something similar in C? [This question](http://stackoverflow.com/questions/8838800/c-determine-if-class-is-comparable) seems to be related, perhaps it is useful? — Krease, Jan 24 '14 at 05:54
Make a copy (`malloc`, `memcpy`) and then sort the copy (`qsort`)? — Heinzi, Jan 24 '14 at 05:59
memcpy from string.h and qsort from stdlib.h will solve your problem. — jfly, Jan 24 '14 at 06:13

Inisheer · Answer 1 · 2014-01-24T20:12:06.660

4

You can use qsort.

Edited to include changes to the OP's question.

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

typedef struct tagPentry
{
    int a, b;
    char c;
} pentry;

/* Function used to compare the structs via qsort in 
the main() method */
int compare(const void *a, const void *b)
{
    pentry* p_a = (pentry*)a;
    pentry* p_b = (pentry*)b;

    /* Here, the compare function sorts based on the value of a 
    If p_a.a == p_b.a, then it will also sort by b*/
    if (p_a->a < p_b->a)
        return -1;
    if (p_a->a > p_b->a)
        return 1;
    else /* a is equal, so compare b */
    {
        if (p_a->b < p_b->b)
            return -1;
        if (p_a->b > p_b->b)
            return 1;
        return 0;
    }
}

int main(int argc, char** argv)
{
    /* Original array */
    pentry p[5];
    p[0].a = 1; p[0].b = 2; p[0].c = 'a';
    p[1].a = 4; p[1].b = 8; p[1].c = 'z';
    p[2].a = 2; p[2].b = 7; p[2].c = 'c';
    p[3].a = 2; p[3].b = 1; p[3].c = 'e';
    p[4].a = 5; p[4].b = 6; p[4].c = 'b';

    /* Temp array for output */
    pentry ptemp[5];
    memcpy(ptemp, p, sizeof p);

    /* Sort temp array */
    qsort(ptemp, 5, sizeof(pentry), compare);

    /* Print output */
    for (int i = 0; i < 5; ++i)
    {
        printf("%d %d %c\n", ptemp[i].a, ptemp[i].b, ptemp[i].c);
    }

    return 0;
}

The compare function returns an integer depending on the comparison of the data within the structs. In this example, you can simply subtract the pentry.a values of each struct to determine which is lower. Since we want to compare pentry.b if, and only if, pentry.a for both structs are the same, we use a conditional if statement to compare the pentry.b values when necessary.

edited Jan 24 '14 at 20:12

answered Jan 24 '14 at 06:12

Inisheer

20,376
9
50
82

I modified the question a bit, can you please elaborate on that? Thanks – clever_bassi Jan 24 '14 at 06:17
1

@ayushi Sure, changed. – Inisheer Jan 24 '14 at 06:22
Though it is not an issue with the specific sample data the OP provided, the comparator via-subtraction can cause underflow (or overflow) if the members of the structure are valued to do so. ex: `INT_MIN/2` and `INT_MAX/2+2`, or `INT_MIN` and any positive number, etc. For this reason it is advised *not* to use short-cut subtraction and rather use genuine logical comparison, enforcing a strict weak order, and return -1, 0 or 1. Better to start the habit early than discover it by-defect later down the road. – WhozCraig Jan 24 '14 at 06:34
@WhozCraig Correct. Updated in the even the sample data is not a true example of the data set he/she is working with. – Inisheer Jan 24 '14 at 06:45
Why not use an array of pointers to the items in the original array. Saves quite some memory if the struct becomes bigger. – invalid_id Jan 24 '14 at 06:48
The question was tagged 'shallow-copy' but this solution is actually using a deep copy. Perhaps you could improve it by making the ptemp an array of pointers to the original structs and then sort that? – harmic Jan 24 '14 at 06:48
@Inisheer I am new to C. Can you explain int compare(const void *a, const void *b). Is this comparing the two structures a and b or do there a and b refer to the elements in the structure (int a and int b as i had specified in the question) ? – clever_bassi Jan 24 '14 at 07:12
@ayushi It compares 2 of whatever are passed in to the parameters. In our case, it's two structs of type pentry. qsort doesn't know how to compare two objects. Therefore, you must supply it a compare method (you don't have to name it that) so the qsort function knows how to sort. – Inisheer Jan 24 '14 at 16:44

woolstar · Accepted Answer · 2014-01-24T07:30:44.540

To sort the items without messing with the original array, create a second array of references:

struct pentry plist[]= { { 1, 2, 'a' }, { 4, 8, 'z' }, { 2, 7, 'c' }, { 2, 1, 'e' }, { 5, 6, 'b' } ;
struct pentry (* pref)[5] ;

int compare( const struct pentry ** px, const struct pentry ** py )
{
  return ( (** px).a == (** py).a ) ? ( (** py).b - (** px).a ) : ( (** py).a - (** px).a ) ;
}

void dosort( struct pentry ** zdest, struct pentry * asrc, int n )
{
  int i ;
  struct pentry ** fill ;

  for ( i= n, fill= zdest ; ( i -- ) ; ) { *( fill ++)= asrc ++ ; }
  qsort( zdest, n, sizeof( * zdest ), compare ) ;
}

void show_sorted( struct pentry ** aref, int n )
{
  while ( n -- )
  {
    printf("%d %d %c\n", (** aref).a, (** aref).b, (** aref).c ) ;
    ++ aref ;
  }
}

int main()
{
  dosort( pref, plist, sizeof( plist) / sizeof( * plist)) ;
  show_sorted( pref, sizeof( plist) / sizeof( * plist)) ;
  return 0 ;
}

score 1 · Answer 3 · answered Jan 24 '14 at 06:14

With a hope you know sorting a simple integer array,

make a function that take two structures and decide on your own criteria which is greatest or in other words should come first than loop through the structure array with following code,

if( priorityof(arr[j],arr[j+1]) ==0)
SWAP

your function should return zero if they need to SWAP else return 1

Sorting of an array

3 Answers3