Sort an array of structures

sassy99 · #1 25-Nov-2006, 22:54

hi i need to sort this array of structures

i tried using bubble sort but there is something wrong with wut i have so far...it is outputting a few of the elements in the array and repeating them more than once

here is my code (i attached the input file im reading from)

CPP / C++ / C Code:

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

typedef struct {
    int size;
    char name[21];
		int boxnumber;
}item;


void swap(item *a, item *b){

  item tmp;

  tmp = *a;
  *a = *b;
  *b = tmp;
}

void bubbleSort(item a[], int size){

int i, j;

  for (i=0; i<size-1; i++){
    for (j=size-1; j>i; j--)
      if
(a[j].size < a[j-1].size)
        swap(&a[j], &a[j-1]);

}
}


int main() {
    int s,n; //s=boxsize, n=number of items in box
		int i;



	FILE * iFile;
	iFile = fopen ("inputzou.txt","r");

	fscanf (iFile, "%d, %d", &s, &n);


		printf ("%d, %d\n", s, n);

	for (i=0;i<=n;i++){
item *array;
    array=(item *) malloc (sizeof(item));
array[i].boxnumber=0; //initialize boxnumber to 0

		fscanf(iFile, "%s %d", array[i].name, &array[i].size);


bubbleSort(array,n);

printf("%s %d\n", array[i].name, array[i].size);




		free(array);
	}
fclose(iFile);



	return 0;


}

davekw7x · #2 26-Nov-2006, 00:06

Quote:

Originally Posted by sassy99

hi i need to sort this array of structures

Here is how I might approach the problem:

Code:

1. Read value of n
2. Allocate storage for an array of n structs: malloc(n * sizeof(item)
3. Execute the following loop for i = 0 up to but not including n:
    read elements array[i].name and array[i].size
4. Sort the array
5. Print the sorted array
6. Free the storage obtained from malloc()
7. Quit

Now examine your code. Is that what it is doing? (Answer: no.)

Start with a file with only a few elements and make sure that the array is read in correctly and sorted correctly. (Printing out the values as each one is read, as you do, is a very good idea to make sure the items are getting into the array correctly.)

Regards,

Dave

mathematician · #3 26-Nov-2006, 05:17

Before I wrote my own sorting routine I would have a look to see if qsort could do the job, but then I'm lazy. (usually declared in stdlib.h)

anders · #4 13-Feb-2007, 04:46

Hi, I'm trying to sort an array of pointer to structs using qsort. I've written my own compare-function, which is supposed to compare an int member of the struct.

My problem is that it doesn't work. The be able to see the content in the structs I wrote a small function for this (printTree). When I use an element of the array (a pointer to struct) as an argument to the printTree function I get the correct output. But if do the printout in the beginning of the compare function, it prints out something completely different from what I expected.

Here's the code (it's C, not C++).

CPP / C++ / C Code:

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

#define NUMBERS 4

typedef struct _Tree {
    struct _Tree *left;
    struct _Tree *right;
    int value;
} Tree;

/* Print the struct in a human-readable way */
void printTree(Tree *t) {
    if (t->left == NULL)
        printf("t->left  == NULL\n");
    else
        printf("t->left  != NULL\n");
    if (t->right == NULL)
        printf("t->right == NULL\n");
    else
        printf("t->right != NULL\n");
    printf("t->value  =  %d\n", t->value);
}

int compareTree(const void *v1, const void *v2) {
    Tree *t1 = (Tree*) v1;
    Tree *t2 = (Tree*) v2;
    /* The following printTree's are the strange ones! */
    printf("t1:\n");
    printTree(t1);
    printf("t2:\n");
    printTree(t2);
    /* A lot of printf's to track which if-statement was true... */
    if (t1 == NULL) {
        printf("compareTree return case 1\n");
        return 1;
    }
    if (t2 == NULL) {
        printf("compareTree return case 2\n");
        return -1;
    }
    if (t1->value < t2->value) {
        printf("compareTree return case 3\n");
        return 1;
    }
    if (t1->value == t2->value) {
        printf("compareTree return case 4\n");
        return 0;
    }
    printf("compareTree return case 5\n");
    return -1;
}


int main(void) {
    Tree* arr[NUMBERS];

    /* Fill the array */
    for (int i = 0; i < NUMBERS; i++) {
        if ((arr[i] = calloc(1, sizeof(Tree))) == NULL) {
            printf("calloc error\n");
            return 1;
        }
        arr[i]->value = 2 * (i + 1);  /* Just a test value */
    }
    
    /* Print the array */
    printf("The structs before sorting:\n");
    for (int i = 0; i < NUMBERS; i++) {
        printf("\narr[%d]:\n", i);
        printTree(arr[i]);
    }
     
    /* Sort the array */
    qsort(arr, NUMBERS, sizeof(Tree*), compareTree);
    
    /* Print the array */
    printf("The structs after sorting:\n");
    for (int i = 0; i < NUMBERS; i++) {
        printf("\narr[%d]:\n", i);
        printTree(arr[i]);
    }

    return 0;
}

As I see it, the array (and the structs) is fine before the qsort statement, but then something happens inside the compareTree function.

Does this have to do with argument passing (call-by-value/call-by-reference) or some properties of pointers? I've done a lot in Java, but not so much in C, so I can't see if there is any pointer-related problems. Could it be something with the allocation of memory?

All ideas to solve this are welcome!

mathematician · #5 13-Feb-2007, 10:31

In the compareTree function v1 and v2 aren't pointers to Tree structures, but pointers into and array (arr[]), and each element of that array contains a pointer to a Tree structure.

davekw7x · #6 13-Feb-2007, 10:58

Quote:

Originally Posted by anders

My problem is that it doesn't work.
...
Does this have to do with argument passing (call-by-value/call-by-reference) or some properties of pointers? Could it be something with the allocation of memory?

It has to do with the way that qsort accesses the things that are being sorted.

To sort an array of structs in memory:
The function qsort() uses its first argument as a pointer to the beginning of a block of contiguous memory that holds something that will be used to access the data items. If the data items are guaranteed to be in contiguous memory (like an array of structs), you can pass the address of the first item. The qsort function will pass pointers to the data items to your comparison function, and will swap the data items (the structs) as it needs to in order to effect the sort.

The second argument to qsort will be the number of data items you have, and the third argument will be the size of a data item. The fourth argument, of course is the address of your comparison function. Your comparison function will be written to take care of the fact that its arguments are addresses of data items (pointer to data items).

To sort an array of structs in memory by using pointers:
If the data items are accessed through an array of pointers, you pass the address of the first pointer. The qsort function will pass addresses of the pointers to your comparison function and will swap the pointers as it needs to in order to effect the sort. Your comparison function will be written to take care of the fact that its arguments are addresses of pointers to data items (pointer to pointer to struct).

Important warning:
Since you allocated the structs with separate calls to calloc, there is no guarantee that the blocks for them will be in contiguous memory (although they may be). Furthermore, the size of the blocks from calloc will be at least as large as the number of bytes that your requested, but very well may be larger. So: there is no way (no way) to properly use qsort with the way you set up your array of pointers to structs.

To use pointers, for sorting (so that qsort can swap pointers rather than swapping the entire structs):
1. Allocate storage for the structs in contiguous memory. (Either declare an array or declare a pointer to struct and malloc/calloc memory for the entire array of structs.)

2. Allocate storage for an array of pointers to the struct and initialize each pointer to the address of a struct in the array of structs. The pointers will be in contiguous memory, but the things that they point to will not necessarily be in contiguous blocks. That's OK; qsort will be using the pointers.

3. Pass the address of the first pointer and size of pointer to qsort.

4. The qsort function will be working with the addresses of your pointers, so make your comparison routine work with the "pointer to pointer" things that are passed as its arguments.

CPP / C++ / C Code:

/* sorting an array of structs using pointers */
#include <stdio.h>
#include <stdlib.h>

#define NUMBERS 4

typedef struct _Tree {
    struct _Tree *left;
    struct _Tree *right;
    int value;
} Tree;

int compareTree(const void *v1, const void *v2);
void printTree(Tree * t);

int main()
{
    Tree **arr;  /* will be used as an array of pointers to structs */
    Tree *array; /* The base of the array of structs in memory      */
    int i;

    printf("sizeof(Tree) = %d\n", sizeof(Tree));

    /* This is the array of structs in contiguous memory */

    arr = calloc(NUMBERS, sizeof(Tree *));
    if (arr == NULL) {
        printf("Can't allocate %d bytes for arr\n", NUMBERS * sizeof(Tree *));
        return 0;
    }
    else {
        printf("Allocated %d bytes for arr\n\n", NUMBERS * sizeof(Tree *));
    }

    array = calloc(NUMBERS, sizeof(Tree));
    if (array == NULL) {
        printf("Couldn't allocate %d bytes for array\n", NUMBERS*sizeof(Tree));
        return 0;
    }

    printf("Allocated %d bytes for array\n", NUMBERS*sizeof(Tree));

    /* 
     * initialize array of pointers to point to the structs in array
     * and initialize the value of each 
     */
    for (i = 0; i < NUMBERS; i++) {
        arr[i] = array+i;                   /* array+i is equal to &array[i] */
        arr[i]->value = 2 * (i + 1);        /* Just a test value */
        printf("arr[%d] = %p\n", i, (void *)arr[i]);
    }
    printf("\n");



    /* 
     * for debug purposes, access the elements through the pointers
     * and compare with values in the array of structs in memory
     * 
     * pointers and structs are lined up
     */
    printf("Before sorting:\n");
    printf("  The relationship between the pointers and the array:\n");
    for (i = 0; i < NUMBERS; i++) {
        printf("    arr[%d]->value = %d; array[%d].value = %d\n",
                i, arr[i]->value, i, array[i].value);
    }
    printf("\n");

    /* Print the array using printTree with the pointer array*/
    printf("  Using printTree:\n");
    for (i = 0; i < NUMBERS; i++) {
        printf("    arr[%d]: ", i);
        printTree(arr[i]);
    }
    printf("\n\n");

    /* Sort the array */
    qsort(arr, NUMBERS, sizeof(Tree*), compareTree);

    /* Print the array using printTree with the pointer array*/

    printf("\nAfter sorting:\n");
    printf("  Using printTree:\n");
    for (i = 0; i < NUMBERS; i++) {
        printf("    arr[%d]: ", i);
        printTree(arr[i]);
    }
    /* 
     * for debug purposes, access the elements through the pointers
     * and compare with values in the array of structs in memory
     * 
     * Pointers have been swapped; the original structs are still
     * in place.
     */
    printf("  The relationship between the pointers and the array:\n");
    for (i = 0; i < NUMBERS; i++) {
        printf("    arr[%d] = %d; array[%d].value = %d\n",
                i, arr[i]->value, i, array[i].value);
    }
    printf("\n");

    return 0;
}

/* Print the struct value in a human-readable way */
void printTree(Tree * t)
{
    printf("t->value  =  %d\n", t->value);
}

int compareTree(const void *v1, const void *v2)
{
    Tree *t1 = *(Tree **)v1;
    Tree *t2 = *(Tree **)v2;

    /* The following printTree's are the strange ones! */
    printf("In compareTree: t1 = %p, t2 = %p\n", (void *)t1, (void *)t2);
    printf("t1: ");
    printTree(t1);
    printf("t2: ");
    printTree(t2);
    /* A lot of printf's to track which if-statement was true... */
    if (t1->value < t2->value) {
        return 1;
    }
    if (t1->value == t2->value) {
        return 0;
    }
    return -1;
}

Output (gcc on Windows XP)

Code:

sizeof(Tree) = 12
Allocated 16 bytes for arr

Allocated 48 bytes for array
arr[0] = 00321778
arr[1] = 00321784
arr[2] = 00321790
arr[3] = 0032179C

Before sorting:
  The relationship between the pointers and the array:
    arr[0]->value = 2; array[0].value = 2
    arr[1]->value = 4; array[1].value = 4
    arr[2]->value = 6; array[2].value = 6
    arr[3]->value = 8; array[3].value = 8

  Using printTree:
    arr[0]: t->value  =  2
    arr[1]: t->value  =  4
    arr[2]: t->value  =  6
    arr[3]: t->value  =  8


In compareTree: t1 = 00321784, t2 = 00321778
t1: t->value  =  4
t2: t->value  =  2
In compareTree: t1 = 00321790, t2 = 00321778
t1: t->value  =  6
t2: t->value  =  2
In compareTree: t1 = 0032179C, t2 = 00321778
t1: t->value  =  8
t2: t->value  =  2
In compareTree: t1 = 00321784, t2 = 0032179C
t1: t->value  =  4
t2: t->value  =  8
In compareTree: t1 = 00321790, t2 = 00321784
t1: t->value  =  6
t2: t->value  =  4
In compareTree: t1 = 00321790, t2 = 0032179C
t1: t->value  =  6
t2: t->value  =  8

After sorting:
  Using printTree:
    arr[0]: t->value  =  8
    arr[1]: t->value  =  6
    arr[2]: t->value  =  4
    arr[3]: t->value  =  2
  The relationship between the pointers and the array:
    arr[0] = 8; array[0].value = 2
    arr[1] = 6; array[1].value = 4
    arr[2] = 4; array[2].value = 6
    arr[3] = 2; array[3].value = 8

Notice that the structs themselves are still in their original positions; only the pointer values have changed. That was the point of this little exercise.

Regards,

Dave

anders · #7 13-Feb-2007, 11:45

Dave, thank you very much for your great answer! I will read it through carefully again and try to solve my problem.

anders · #8 13-Feb-2007, 17:39

If I look at what I want to do with from an objectoriented point of view, as in Java, I have a number of objects. I need to create and delete these objects dynamically, but there will never be more than MAX_SIZE objects existing at the same time, so I could use an array to reference them. Something like

array[i] = new Tree(...);
counter++;

when creating a new object and

array[i] = null;
counter--;

when deleting an object (i is guaranteed to never exceed MAX_SIZE). The length of the array is MAX_SIZE, but I use a counter to indicate the number of objects currently in the array.

To sort this array, figuring out which object is "greater" could be done something like

if (array[a].getOrderProperty() < array[b].getOrderProperty()) {
...
} else ...

and then each swap would be done like this

Tree tmp = array[a];
array[a] = array[b];
array[b] = tmp;

Back to C, the "objects" are the Tree structs, and I need to create (and delete) these structs dynamically. However there will never be more than MAX_SIZE structs at the same time, so the array of pointers to structs can have a fixed number of elements. But most of the time some of these pointers will point to null. I need a counter to indicate the number of pointers actually pointing to a struct.

When it comes to sorting I don't care where the structs are stored as long as I have pointers to them. The pointers are stored in the (contiguously allocated) array, but as some of them points to null those shouldn't be included in the sorting. (Even though I use pointers for technical reasons, they refer to some "real thing", and I don't wan't to sort "things" not existing.)

The arguments to qsort would now be:

base address of array of pointers to structs
counter (number of non-null pointers in the array above)
sizeof(pointer to struct)
compare function (arguments to this function are pointers to elements in the pointer to structs array, and the comparison is based on member values of the structs)

Finally my question, does this method work in C? According to your "important warning", there is no guarantee that qsort will work properly if the structs aren't contiguously allocated. If that's true, and it isn't enough if the pointers to structs are contiguously allocated, how should one then solve this problem? Do I really have to allocate an array of structs with MAX_SIZE elements, and include a way to handle "null structs" in the compare function? If the structs has many members and MAX_SIZE is large, that would take a lot of memory.

Regards,
Anders

davekw7x · #9 13-Feb-2007, 22:52

Quote:

Originally Posted by anders

Do I really have to allocate an array of structs with MAX_SIZE elements, and include a way to handle "null structs" in the compare function? If the structs has many members and MAX_SIZE is large, that would take a lot of memory.

qsort is a standard library function and was the subject of your incorrect program. I have tried to indicate two ways of using it: directly swapping entire structs (in which case the structs must be in a contiguous memory block). Or by swapping pointers (the pointers in the array are contiguously located but the structs can be stored anywhere that you can point to). In general, it would be more efficient (time-wise) to swap pointers than to swap entire structs and that's a big reason for using pointers.

With either method, dIfferent compare functions could operate on different fields so that the data base can be presented as being sorted on different keys. That's a big feature of qsort: the ability to use different comparison functions. (And from a pedagogical point of view qsort is a very practical illustration of the use of pointers to functions.)

You don't have to use qsort, you know.

You could make a linked list that grows and shrinks as the situation warrants, and use your own implementation of any sorting algorithm that suits your fancy and suits your needs.

Very large data bases may require something other than a canned library function for effective sorting (or any other type of manipulation).

Often there is a tradeoff between time, storage requirements and complicatedness of the program (and therefore the sanity of the programmer).

Regards,

Dave

anders · #10 15-Feb-2007, 07:49

Dave, the thing I didn't understand when I posted my first question was that the array of pointers (as first argument to qsort) had to be contiguous allocated. (But when thinking more of it, if that not had been the case, why should one then need to give the size argument to qsort?)

Quote:

To use pointers, for sorting (so that qsort can swap pointers rather than swapping the entire structs):

Allocate storage for the structs in contiguous memory. (Either declare an array or declare a pointer to struct and malloc/calloc memory for the entire array of structs.)
Allocate storage for an array of pointers to the struct and initialize each pointer to the address of a struct in the array of structs. The pointers will be in contiguous memory, but the things that they point to will not necessarily be in contiguous blocks. That's OK; qsort will be using the pointers.
Pass the address of the first pointer and size of pointer to qsort.
The qsort function will be working with the addresses of your pointers, so make your comparison routine work with the "pointer to pointer" things that are passed as its arguments.

First you said I had to allocate the structs contiguously. That was the thing that made me confused. But in the second point, you said that the things the pointers point to will not necessarily be in contiguous blocks...

Another thing that I didn't realize when I posted my first question was the "pointer to pointer" arguments passed to the compare function.

Anyway, I have now solved my problem, and I would like to once again say thank you for your help!

Regards,
Anders

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
printing an array of structures	nic.nmd	C Programming Language	3	19-Oct-2006 08:53
Need help deleting the last element in the array	headphone69	C++ Forum	2	15-Mar-2006 20:31
Merge and Heap...which is really faster	silicon	C++ Forum	0	10-May-2005 14:46
Sorting Algorithms by Time	silicon	C++ Forum	4	02-May-2005 22:54
template comiling problems - need expert debugger!	crq	C++ Forum	1	01-Feb-2005 22:26

Sort an array of structures

Re: sort an array of structures

Re: sort an array of structures

Re: sort an array of structures

Re: sort an array of structures

Re: sort an array of structures

Re: sort an array of structures

Re: sort an array of structures

Re: sort an array of structures

Re: sort an array of structures