Sorting structures lexicographically

Question

I am swapping structure lexicographically by name. Is there any way to improve the code when the structure entries are heavy.

Here is the code

#include<stdio.h>
#include<string.h>
struct College
{
    char name[100];
    char city[100];
    int yearOfEstablishment;
    float passPercentage;
};
void displayCollegeDetails(struct College c)
{
    printf("Name : %s\n",c.name);
    printf("City: %s\n",c.city);
    printf("Year of establishment : %d\n",c.yearOfEstablishment);
    printf("Pass percentage: %.2f\n",c.passPercentage);
}
void swap(struct College *a,struct College *b)
{
    struct College temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
int main()
{

    int n,i,j;
    //char name[100],city[100];
    //float paasPercentage;
    printf("Enter the number of colleges\n");
    scanf("%d",&n);
    struct College c[n];
    if(n<=0)
    {
        printf("Invalid Input\n");
        return 0;
    }

    for(i=0; i<n; i++)
    {
        fflush(stdin);
        printf("Enter the details of college %d\n",i+1);
        printf("Enter name\n");
        scanf("%s",c[i].name);
        printf("Enter city\n");
        scanf("%s",c[i].city);
        printf("Enter year of establishment\n");
        scanf("%d",&c[i].yearOfEstablishment);
        printf("Enter pass percentage\n");
        scanf("%f",&c[i].passPercentage);
    }
    for(i=0; i<n-1; i++)
    {
        for(j=i+1; j<n; j++)
        {
            if(strcmp(c[i].name,c[j].name)>0)
            {
                swap(&c[i],&c[j]);
            }
        }
    }
    printf("Details of colleges\n");
    for(i=0; i<n; i++)
    {
        fflush(stdin);
        printf("College %d\n",i+1);
        displayCollegeDetails(c[i]);
    }
    return 0;
    }

Answer 1

Is there any way to improve the code when the structure entries are heavy.

1st idea is to use a different sort method. This code runs in O(n*n) time with the for(i=0; i<n-1; i++) for(j=i+1; j<n; j++) loops.

Various sorts operate in O(n*lo2(n)) time and are not too difficult to code.

2nd idea: Make an array of pointers to the list and sort that. Then only pointers need to be moved during the heavy part of the algorithm. When done, the final list can then be arranged per the pointer list.

3rd. Use a hash table for even faster sorting. Of course, this is more code and complexity.

---

General coding observations

1. fflush(stdin); is non-portable. Code should be able to be written without it. Better to use fgets() and then scan the string.

2. printf("Enter city\n"); scanf("%s",c[i].city); is problematic for 1) it does not limit input to 99 characters as needed per the buffer size. Many cities have a space in their name "New York" and "%s" does not save spaces. Use fgets() and lop off the tailing '\n' as needed. name[] too.

3. Best to validate input: check return value from *scanf() functions.

4. The check it too late. Do it before declaring College[]

   // struct College c[n];
   if(n<=0) 
     ...
   struct College c[n];
   

---

A point on improved sorting methods.

By sorting on name[] only, code could have multiple entries with the same name like "John Adams". With OP's slow O(n*n) method, a benefit to it is that it is a stable sort. OP's sorting would not change the sequence concerning ties.

Now consider the standard function qsort() with a simple compare function that only reference name[], then the order of entries on ties is not guaranteed.

"If two elements compare as equal, their order in the resulting sorted array is unspecified." C11 §7.22.5.2

Many fast methods do not guarantee stability.

A classic solution is to include a unique index number with each College[]. Then when there is a tie on the name[], the index could be the tie breaker, ensuring a stable sort. With the reference table idea far above, possible the "index" could be the College[] address (a pointer) in a clever usage, thus incurring no additional memory cost.

Answer 2

Sort pointers rather than objects

    struct College c[n];

Rather than make an array of struct values, make an array of pointers.

    struct College *colleges[n];

Then change things like

        scanf("%s",c[i].name);

to

        scanf("%s", c[i]->name);

and replace

                swap(&c[i],&c[j]);

with

                  struct College *temp = c[i];
                  c[i] = c[j];
                  c[j] = temp;

Then the swaps are only as costly as swapping pointers regardless of the size of the struct.

Favor standard implementations

Also, if you are worried about efficiency, you might better use the provided qsort than manually implementing a bubble sort. Call it something like

    qsort(c, n, sizeof *c, compareCollegeNames);

with something like

int compareCollegeNames(const void * a, const void * b) {
    return strcmp(((struct College *)a)->name, ((struct College *)b)->name);
}