sorting array of structures using bubble sort - how to speed up exchange of struct members
Solution 1
int i, j, tmp;
words temp;
for (i = 0; i < max; i++)
{
for (j = 0; j < max - i; j++)
{
if (strcmp(array[j].word, array[j + 1].word) > 0)
{
memcpy(&temp, array[j], sizeof(words));
memcpy(array[j], array[j + 1], sizeof(words));
memcpy(array[j + 1], &temp, sizeof(words));
}
}
}
Solution 2
If your concern is with the performance in the swapping process, you should consider and array of pointers of type the struct you are using:
struct your_stuct *arr[MAX];
If you set correctly this array, the swap will change only the memory addresses rather than the struct contents and it could run faster:
Within your inner loop you should use:
struct your_struct *temp;
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
Is this what you mean in your question?
Solution 3
Rather than sorting the structs
themselves, create an array of pointers to the structs, and an appropriate comparison function that reads the appropriate values from the struct through the pointer, and sort the list of pointers. Of course, all the extra indirections may mask any performance gain you get from not actually swapping the structs around, since your structs are fairly small, but for large structs, this approach makes a lot of sense.
Comments
-
Peter Cerba about 2 years
I have a structure consisting of two elements
char *word
andint number
. When I want to sort them using bubble sort, I have to write exchange parts for both of them:int i,j,tmp; char * temp; for(i=0; i<max;i++) { for(j=0;j<max-i;j++) { if(strcmp(array[j].word,array[j+1].word)>0) { temp=array[j].word; array[j].word=array[j+1].word; array[j+1].word=temp; tmp=array[j].number; array[j].number=array[j+1].number; array[j+1].number=tmp; } } }
EDIT My struct declaration
typedef struct{ char *word; int number; } words; words *array=NULL;
What if I had n elements in the array ? That would be very time consuming to exchange everything. Is there any way to omit this?
OF COURSE except for other sorting algorithms, which I don't want to use (like
qsort
). -
Peter Cerba almost 12 yearsYes, thanks for suggestion about pointers. Rather than speed I was looking for not writing the exchange of every struct member. 3 lines per member and I imagined having 8 members - that would be 24 lines of code just for replacement. Scary
-
Peter Cerba almost 12 yearsI know
memcpy
but wouldn't come up with an idea to use it for sorting huge structs with ALL their elements. Big thanks!