Home > Mobile >  Sorting Array of Structure by Mutiple Criteria with Bubble Sort in C
Sorting Array of Structure by Mutiple Criteria with Bubble Sort in C

Time:03-20

I'm trying to implement a bubble sort for an array of struct with multiple sorting criteria.

Basically, the program compute how many follower a user has and also how many other users this user is following.

The result should be sorted by the following criteria:

  1. Rank the user by number of followers from highest to lowest.
  2. If the number of followers is equal, rank be the number of follow from highest to lowest.
  3. If criteria 1 and 2 has the same number, sort the user "index" from lowest to highest (like in the case of user 0 and 3).

I have managed to come up with the sort but it only sort by 1 property, which showing in the code, it is sorting by number of follower only. I'm not really sure with is the next step from here.

Also, I'm trying to make the sort a separate function out side of the main(), but it needs access to u[i].node, u[i].nFollower, and u[i].nFollow. And I don't know what is the correct way to do it. Could you please show the the correct syntax to do it, since I'm very new to C.

Thank you very much!

Input:

Enter the number of users: 6
Enter a user (follower): 0
Enter a user (followed by 0): 1
Enter a user (follower): 1
Enter a user (followed by 1): 5
Enter a user (follower): 3
Enter a user (followed by 3): 5
Enter a user (follower): 5
Enter a user (followed by 5): 0
Enter a user (follower): 2
Enter a user (followed by 5): 5
Enter a user (follower): 1
Enter a user (followed by 5): 3
Enter a user (follower): #
Done.

Output without sorting

5 has 3 followers(s) and follows 1 user(s).
0 has 1 followers(s) and follows 1 user(s).
3 has 1 followers(s) and follows 1 user(s).
1 has 1 followers(s) and follows 2 user(s).
4 has 0 followers(s) and follows 0 user(s).
2 has 0 followers(s) and follows 1 user(s).

Desired output:

5 has 3 followers(s) and follows 1 user(s).
1 has 1 followers(s) and follows 2 user(s).
0 has 1 followers(s) and follows 1 user(s).
3 has 1 followers(s) and follows 1 user(s).
2 has 0 followers(s) and follows 1 user(s).
4 has 0 followers(s) and follows 0 user(s).
#include <stdio.h>
#include "WGraph.h"

typedef struct User {
    int node;
    int nFollower;
    int nFollow;
} User;

int main (void) {
    Edge e = {0, 0, 1};
    int nUsers;

    printf("Enter the number of users: ");
    scanf("%d", &nUsers);
    
    Graph g = newGraph(nUsers);

    printf("Enter a user (follower): ");
    while (scanf("%d", &e.v) == 1) {
        printf("Enter a user (followed by 0): ");
        scanf("%d", &e.w);
        insertEdge(g, e);
        printf("Enter a user (follower): ");
    }
    printf("Done.\n");

    //showGraph(g);


    int nV = numOfVertices(g);
    int countFollower;
    int countFollow;
    User u[nV];
    printf("Ranking by follower base:\n");
    for (int i = 0; i < nV; i  ) {
        countFollow = 0;
        countFollower = 0;
        u[i].node = i;
        for (int j = 0; j < nV; j  ) {
            if (adjacent(g, j, i) != 0) {
                countFollower  ;
            }

            if (adjacent(g, i, j) != 0) {
                countFollow  ;
            }
        }
        u[i].nFollower = countFollower;
        u[i].nFollow = countFollow;
    }
    
    //Sort and update array of struct
    int temp1;
    int temp2;
    int temp3;
    for (int i = 0; i < nV; i  ) {
        for (int j = 0; j < nV; j  ) {
            if (u[i].nFollower > u[j].nFollower) {
                temp1 = u[j].nFollow;
                temp2 = u[j].nFollower;
                temp3 = u[j].node;
                u[j].nFollow = u[i].nFollow;
                u[i].nFollow = temp1;
                u[j].nFollower = u[i].nFollower;
                u[i].nFollower = temp2;
                u[j].node = u[i].node;
                u[i].node = temp3;
            }
        }
    }

    for (int i = 0; i < nV; i  ) {
        printf("%d has %d followers(s) and follows %d user(s).\n", u[i].node, u[i].nFollower, u[i].nFollow);
    }

    //freeGraph(g);
    return 0;
}

CodePudding user response:

Just check for the condition while sorting in bubble sort

for (int i = 0; i < nV; i  ) {
                for (int j = 0; j < nV; j  ) {
                        if ((u[i].nFollower > u[j].nFollower) || \
                                        (u[i].nFollower == u[j].nFollower && u[i].Follow > u[j].Follow) || \ 
                                        (u[i].nFollower == u[j].nFollower && u[i].Follow == u[j].Follow && i < j)) {
                                temp1 = u[j].nFollow;
                                temp2 = u[j].nFollower;
                                temp3 = u[j].node;
                                u[j].nFollow = u[i].nFollow;
                                u[i].nFollow = temp1;
                                u[j].nFollower = u[i].nFollower;
                                u[i].nFollower = temp2;
                                u[j].node = u[i].node;
                                u[i].node = temp3;
                        }
                }
        }

here we are iterating n-1 time and each time we iterate we skip the elements which are in proper order. Instead of using temperory variable I am using xor operator to swap elements.

 for (int i = 0; i < nV-1; i  ) {
                for (int j = 0; j 1 <= nv-1-i; j  ) {
                        if ((u[j].nFollower > u[j 1].nFollower) || \
                                        (u[j].nFollower == u[j 1].nFollower && u[j].Follow > u[j 1].Follow)) {

                                u[j].nFollow ^= u[j 1].nFollow;
                                u[j 1].nFollow ^= u[j].nFollow;
                                u[j].nFollow ^= u[j 1].nFollow;

                                u[j].nFollower ^= u[j 1].nFollower;
                                u[j 1].nFollower ^= u[j].nFollower;
                                u[j].nFollower ^= u[j 1].nFollower;

                                u[j].node ^= u[j 1].node;
                                u[j 1].node ^= u[j].node;
                                u[j].node ^= u[j 1].node;
                        }
                }
        }
  • Related