Trying to sort a list

This is a discussion on Trying to sort a list within the C Programming forums, part of the General Programming Boards category; Ello. I'm writing a program in which we are required to sort a guest list by priority level, then by ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    81

    Trying to sort a list

    Ello. I'm writing a program in which we are required to sort a guest list by priority level, then by last name and first name. So far I have been able to sort the priority levels into the correct order, but I'm not sure how to carry the other elements along with it

    Here's the file we are reading from:
    Code:
    10 30
    BEN JOHNSON 4 2
    DOUG ESPINOSA 3 2
    SARAH TELLINGER 5 3
    GRANT THOMPSON 5 2
    JENNIFER WEST 7 6
    JACKSON JOHNSON 1 5
    MARTY MCFLY 4 1
    ELIZABETH JAMES 2 6
    MICKEY MOUSE 2 4
    RAJ SHAH 2 5
    The first two numbers are the amount of families known and the second number is the capacity of the room. Below that, it goes (in order): First Name, Last Name, Family Members, Priority level.

    Here is my code:
    Code:
    #include <stdio.h>
    #include <stdio.h>
    
    const int MAX_NAME_LENGTH = 20;
    
    int Families_Known(FILE *ifp)
    {
        int families;
    
        fscanf(ifp, "%d", &families);
    
        return families;
    }
    
    int Hall_Capacity(FILE *ifp)
    {
        int capacity;
    
        fscanf(ifp, "%d", &capacity);
    
        return capacity;
    }
    
    void Read_And_Store(FILE *ifp, int FAMILIES_KNOWN, char First_Name[][MAX_NAME_LENGTH], char Last_Name[][MAX_NAME_LENGTH], int Family_Members[], int Priority[])
    {
        int i;
    
        for(i = 0; i < FAMILIES_KNOWN; i++)
        {
            fscanf(ifp, "%s", First_Name[i]);
            fscanf(ifp, "%s", Last_Name[i]);
            fscanf(ifp, "%d", &Family_Members[i]);
            fscanf(ifp, "%d", &Priority[i]);
        }
    }
    
    void Print_Array(int FAMILIES_KNOWN, char First_Name[][MAX_NAME_LENGTH], char Last_Name[][MAX_NAME_LENGTH], int Family_Members[], int Priority[])
    {
        int i;
    
        for(i = 0; i < FAMILIES_KNOWN; i++)
        {
            printf("%s ", First_Name[i]);
            printf("%s ", Last_Name[i]);
            printf("%d ", Family_Members[i]);
            printf("%d", Priority[i]);
            printf("\n");
        }
    }
    
    int Compare_Priority(int *Priority1, int *Priority2)
    {
        if(*Priority1 == *Priority2)
        {
            return 0;
        }
    
        else if(*Priority1 < *Priority2)
        {
            return -1;
        }
    
        else
        {
            return 1;
        }
    }
    
    void Swap_Priority(int *Priority1, int *Priority2)
    {
        int tmp;
    
        tmp = *Priority1;
        *Priority1 = *Priority2;
        *Priority2 = tmp;
    
    }
    
    void Sort_Priority(int FAMILIES_KNOWN, int Priority[])
    {
        int i, j;
    
        for(i = 1; i < FAMILIES_KNOWN; i++)
        {
            for(j = i; j >= 1; j--)
            {
                if(Compare_Priority(&Priority[j], &Priority[j - 1]) < 0)
                {
                    Swap_Priority(&Priority[j], &Priority[j - 1]);
                }
    
                else
                {
                    break;
                }
            }
        }
    }
    
    int main()
    {
    
        FILE *ifp;
        ifp = fopen("allguests.txt", "r");
    
        const int FAMILIES_KNOWN = Families_Known(ifp);
        const int CAPACITY = Hall_Capacity(ifp);
    
        char First_Name[FAMILIES_KNOWN][MAX_NAME_LENGTH];
        char Last_Name[FAMILIES_KNOWN][MAX_NAME_LENGTH];
        int Family_Members[FAMILIES_KNOWN];
        int Priority[FAMILIES_KNOWN];
    
        Read_And_Store(ifp, FAMILIES_KNOWN, First_Name, Last_Name, Family_Members, Priority);
        Print_Array(FAMILIES_KNOWN, First_Name, Last_Name, Family_Members, Priority);
    
        Sort_Priority(FAMILIES_KNOWN, Priority);
    
        printf("---------------------------\n");
        Print_Array(FAMILIES_KNOWN, First_Name, Last_Name, Family_Members, Priority);
    
        fclose(ifp);
    
        return 0;
    }
    When I print it out it looks like this:
    Code:
    BEN JOHNSON 4 2
    DOUG ESPINOSA 3 2
    SARAH TELLINGER 5 3
    GRANT THOMPSON 5 2
    JENNIFER WEST 7 6
    JACKSON JOHNSON 1 5
    MARTY MCFLY 4 1
    ELIZABETH JAMES 2 6
    MICKEY MOUSE 2 4
    RAJ SHAH 2 5
    ---------------------------
    BEN JOHNSON 4 1
    DOUG ESPINOSA 3 2
    SARAH TELLINGER 5 2
    GRANT THOMPSON 5 2
    JENNIFER WEST 7 3
    JACKSON JOHNSON 1 4
    MARTY MCFLY 4 5
    ELIZABETH JAMES 2 5
    MICKEY MOUSE 2 6
    RAJ SHAH 2 6
    As you can see the priority number is sorted correctly. I'm having issues with transferring my logic in how to move the names and family members accordingly along with the priority level in the list, but I'm not trying to alphabetize them yet. Any ideas?

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Normally, you'd use a struct to group together the separate parts, into one object. (Not an OOPs object, but an object).

    If you haven't had structs taught yet (and I'm guessing that is the case, obviously), then you can use parallel arrays (one for the first name, one for the second name, and one for the two numbers. Key idea is that Ben Johnson (for example will be on fnames[0] (Ben), lnames[0] (Johnson), and data[0][0] and data[0][1] with 4 and 1 respectively. This involves a good deal of moving things around, however.

    A rather slick way of doing this, is to move NOTHING, and build up an index table that will SHOW the data as if it were sorted any way you want, but what is actually sorted instead, are simple digits which are used as indices.

    This is a simple example of it, with just one index:

    Code:
    #include <stdio.h>
    
    void printIt(int *a, int *map, int size, int type);
    
    int main(void) {
       int i, j, temp;
       int a[]={3,8,0,4,1,2,6,9,5,7};
       int map[10];
    
       //initialize map
       for(i=0;i<10;i++)
          map[i]=i;
    
       //sort via Substitution sort
       for(i=0;i<10-1;i++) {
          for(j=i+1;j<10;j++) {
             if(a[map[i]] > a[map[j]]) {
                temp = map[i];
                map[i] = map[j];
                map[j] = temp;
             }
          }
       }
       printIt(a, map, 10, 0); //original order
       printIt(a, map, 10, 1); //sorted order
       return 0;
    }
    
    void printIt(int *a, int *map, int size, int type) {
       int i;
       
       if(!type) {
          printf("Original and current actual order in array a[]:\n");
          for(i=0;i<size;i++)
             printf("%2d ", a[i]);
       }
       else {
          printf("array a[] as enumerated with the map array as the index:\n");
          for(i=0;i<size;i++)
             printf("%2d ", a[map[i]]);
       }
       printf("\n\n");
    }
    The numbers in the array are never moved. Only the index array (called map in this case), has values changed.

    I'm guessing that the second option is what you want, (parallel arrays), but it's sometimes good to know that other options exist.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    74
    Hi , i need to know what is the answer of your question because, i have the same question in my project.
    but we shouldnt use pointers,functions,math.h, stdlib.h and other upper things.
    i am dealing with it. The bad thing is using stdlib.h is illegal in our project. Anyway...
    i thought that if want to compare the strings, i should use number, if i need to find the number of characters, i need asci codes,
    i can order the data set by usig the ascii codes.for example,
    tom
    tor
    i find the ascii code of all letters and multiplyed with its digit number,
    for example asci code of t =116, o=111 m=109 r=114
    i used this function. t*100+o*10+m*1
    and t*100+o*10+r*1


    my code is this.So there is one important thing that it is;
    you should combine and equalize your arrays with the ascii code and display them as strings, characters


    Code:
    #include <stdio.h>
    
    int main()
    {
    
    
    int kayit[100];
    char c[5];
    int d,i,i1,i2,j;
    int x=1;
    int tempx;
    int kayit2[100];
    
    
    i2=0;
    for(i2=0;i2<6;i2++)
    {
        gets(c);
        if(c[0]=='*') break;
        d=0;
    
    
        for(i=0;i<=5;i++)
        {
            x=1;
              for(i1=0;i1<=i;i1++)
                {
                    x=x*10;
                    if (i1==0) x=1;
                }
            d=c[5-i]*x+d;
        }
    
    
        printf("asci code  of %s=%d\n",c,d);
        kayit[i2]=d;
    }
    for(i=0;i<6;i++)
    printf("%d\n",kayit[i]);
    for(i=0;i<6;i++) kayit2[i]=kayit[i];
    for(i=0;i<6;i++)
    {
        for(j=0;j<6;j++)
        {
            if (kayit[i]<kayit[j]){
             tempx=kayit[j];
             kayit[j]=kayit[i];
             kayit[i]=tempx;
            }
    
    
        }
    }
    for(i=0;i<6;i++)
    printf("Asci Codes will be ordered as :%d\n",kayit[i]);
    for(i=0;i<6;i++) printf("Asci Codes old                :%d\n",kayit2[i]);
    
    
    
    
    }
    Last edited by rac1; 11-20-2011 at 08:27 AM.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    @Rac1, his assignment is similar, but not the same as yours. Please follow the info I gave you. It will work as you need it.

    @Shukiren, if you are sorting by priority level, every time you make a swap in the priority level, you also need to make the same (index number) swap, in all your other 3 char arrays, also. So if j is 4 and you're swapping priority[4] with priority[3], then:

    Code:
    strcpy(temp_str, first_name[4]);
    strcpy(first_name[4], first_name[3]);
    strcpy(first_name[3], temp_str);
    
    strcpy(temp_str, second_name[4]);
    strcpy(second_name[4],second_name[3]);
    strcpy(second_name[3], temp_str);
    
    tempNum=familyNum[4];
    familyNum[4] = familyNum[3];
    familyNum[3] = tempNum;
    
    tempNum = priority[4];
    priority[4] = priority[3];
    prioirity[3] = tempNum;
    Doesn't matter whether you're sorting first name, second name, family number or priority, it's all the same when it comes to the swaps Every array index that gets swapped, means ALL the arrays indices, have to be swapped, at the same time.

    Otherwise, Ben Johnson might wind up with the priority of Micky Mouse, and the family number from Marty McFly. The record data will be hopelessly jumbled up.

  5. #5
    Registered User
    Join Date
    Sep 2011
    Posts
    81
    Yeah. I was over-thinking the process. Thanks for the help .

  6. #6
    Registered User
    Join Date
    Sep 2011
    Posts
    81
    I just have one issue left: it says: "warning: incompatible implicit declaration of built-in function 'strcpy'" for line 91 which I marked below in the Swap_Name function. I was just curious as to what I did wrong.
    Code:
    #include <stdio.h>
    #include <stdio.h>
    
    const int MAX_NAME_LENGTH = 20;
    
    int Families_Known(FILE *ifp)
    {
        int families;
    
        fscanf(ifp, "%d", &families);
    
        return families;
    }
    
    int Hall_Capacity(FILE *ifp)
    {
        int capacity;
    
        fscanf(ifp, "%d", &capacity);
    
        return capacity;
    }
    
    void Read_And_Store(FILE *ifp, int FAMILIES_KNOWN, char First_Name[][MAX_NAME_LENGTH], char Last_Name[][MAX_NAME_LENGTH], int Family_Members[], int Priority[])
    {
        int i;
    
        for(i = 0; i < FAMILIES_KNOWN; i++)
        {
            fscanf(ifp, "%s", First_Name[i]);
            fscanf(ifp, "%s", Last_Name[i]);
            fscanf(ifp, "%d", &Family_Members[i]);
            fscanf(ifp, "%d", &Priority[i]);
        }
    }
    
    void Print(FILE *ofp, int FAMILIES_KNOWN, int Guests_Invited, char First_Name[][MAX_NAME_LENGTH], char Last_Name[][MAX_NAME_LENGTH], int Family_Members[])
    {
        fprintf(ofp, "%d ", FAMILIES_KNOWN);
        fprintf(ofp, "%d \n", Guests_Invited);
    
        int i;
    
        for(i = 0; i < FAMILIES_KNOWN; i++)
        {
            fprintf(ofp, "%s, ", Last_Name[i]);
            fprintf(ofp, "%s ", First_Name[i]);
            fprintf(ofp, "%d ", Family_Members[i]);
            fprintf(ofp, "\n");
        }
    }
    
    
    int Compare_Priority(int *Priority1, int *Priority2)
    {
        if(*Priority1 == *Priority2)
        {
            return 0;
        }
    
        else if(*Priority1 < *Priority2)
        {
            return -1;
        }
    
        else
        {
            return 1;
        }
    }
    
    int Compare_Name(char name1[], char name2[])
    {
        return strcmp(name1, name2);
    }
    
    void Swap_Number(int *Number1, int *Number2)
    {
        int tmp;
    
        tmp = *Number1;
        *Number1 = *Number2;
        *Number2 = tmp;
    
    }
    
    void Swap_Name(char Name1[], char Name2[])
    {
        char tmp[MAX_NAME_LENGTH];
    
        strcpy(tmp, Name1); //line 91 here
        strcpy(Name1, Name2);
        strcpy(Name2, tmp);
    }
    
    int Sort_Priority(int FAMILIES_KNOWN, int Priority[], int Family_Members[], char First_Name[][MAX_NAME_LENGTH], char Last_Name[][MAX_NAME_LENGTH])
    {
        int i, j;
    
        for(i = 1; i < FAMILIES_KNOWN; i++)
        {
            for(j = i; j >= 1; j--)
            {
                if(Compare_Priority(&Priority[j], &Priority[j - 1]) < 0)
                {
                    Swap_Number(&Priority[j], &Priority[j - 1]);
                    Swap_Number(&Family_Members[j], &Family_Members[j - 1]);
                    Swap_Name(Last_Name[j], Last_Name[j - 1]);
                    Swap_Name(First_Name[j], First_Name[j - 1]);
                }
    
                else
                {
                    break;
                }
            }
        }
    }
    
    int Sort_Alphabetical(int Invited_Families, int Priority[], int Family_Members[], char First_Name[][MAX_NAME_LENGTH], char Last_Name[][MAX_NAME_LENGTH])
    {
        int i, j;
    
        for(i = 1; i < Invited_Families; i++)
        {
            for(j = i; j >= 1; j--)
            {
                if(Compare_Name(Last_Name[j], Last_Name[j - 1]) < 0)
                {
                    Swap_Number(&Priority[j], &Priority[j-1]);
                    Swap_Number(&Family_Members[j], &Family_Members[j - 1]);
                    Swap_Name(Last_Name[j], Last_Name[j - 1]);
                    Swap_Name(First_Name[j], First_Name[j - 1]);
                }
    
                else if(Compare_Name(Last_Name[j], Last_Name[j - 1]) == 0)
                {
                    if(Compare_Name(First_Name[j], First_Name[j - 1]) < 0)
                    {
                        Swap_Name(First_Name[j], First_Name[j - 1]);
                        Swap_Number(&Priority[j], &Priority[j-1]);
                        Swap_Number(&Family_Members[j], &Family_Members[j - 1]);
                    }
                }
    
                else
                {
                    break;
                }
            }
        }
    }
    
    Check_Capacity(int FAMILIES_KNOWN, int CAPACITY, int Family_Members[])
    {
        int i, num_families = 0, num_guests = 0;
    
        for(i = 0; i < FAMILIES_KNOWN; i++)
        {
            num_guests += Family_Members[i];
    
            if(num_guests <= CAPACITY)
            {
                num_families++;
            }
    
            else
            {
                break;
            }
        }
        return num_families;
    }
    
    Num_Guests(int FAMILIES_KNOWN, int Family_Members[])
    {
        int i, num_guests = 0;
    
        for(i = 0; i < FAMILIES_KNOWN; i++)
        {
            num_guests += Family_Members[i];
        }
    
        return num_guests;
    }
    
    int main()
    {
        FILE *ifp;
        ifp = fopen("allguests.txt", "r");
    
        const int FAMILIES_KNOWN = Families_Known(ifp);
        const int CAPACITY = Hall_Capacity(ifp);
    
        char First_Name[FAMILIES_KNOWN][MAX_NAME_LENGTH];
        char Last_Name[FAMILIES_KNOWN][MAX_NAME_LENGTH];
        int Family_Members[FAMILIES_KNOWN];
        int Priority[FAMILIES_KNOWN];
    
        Read_And_Store(ifp, FAMILIES_KNOWN, First_Name, Last_Name, Family_Members, Priority);
    
        fclose(ifp);
    
        Sort_Priority(FAMILIES_KNOWN, Priority, Family_Members, First_Name, Last_Name);
    
        int Invited_Families = Check_Capacity(FAMILIES_KNOWN, CAPACITY, Family_Members);
        int Guests_Invited = Num_Guests(Invited_Families, Family_Members);
    
        Sort_Alphabetical(Invited_Families, Priority, Family_Members, First_Name, Last_Name);
    
        FILE *ofp;
    
        ofp = fopen("finalguestlist.txt", "w");
    
        Print(ofp, Invited_Families, Guests_Invited, First_Name, Last_Name, Family_Members);
    
        fclose(ofp);
    
        return 0;
    }
    Works fine for cases such as: same last name, similar first name. Same First Name, similar last name, etc. (Don't have to worry about same last name same first name because our teacher told us we didn't need to account for that). If you find anything out of the ordinary don't hesitate to bring it up.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You've included stdio.h file twice, and have not included string.h.

    You can't use strcpy without including string.h.

  8. #8
    Registered User
    Join Date
    Sep 2011
    Posts
    81
    oops. lol!

  9. #9
    Registered User
    Join Date
    Sep 2011
    Posts
    81
    Actually. ONE more issue that I've been trying to fix for quite a while. I just can't get it down. If only SOME families from a priority level can be invited and not all of them, that whole priority level is skipped and the guest list immediately stops being filled. I'm having a bit of trouble trying to put the logic into code here (Our teacher added this little fun part of the program last class >.<). I know this code I'm about to post isn't correct and that the while loop doesn't increment the index, but it was the last thing I've tried:
    Code:
    int Check_Capacity(int FAMILIES_KNOWN, int CAPACITY, int Family_Members[], int Priority[])
    {
        int i, num_families = 0, num_guests = 0, count = 0;
    
        for(i = 0; i < FAMILIES_KNOWN; i++)
        {
            count++;
    
            while(Priority[i] == count)
            {
                num_guests += Family_Members[i];
    
                if(num_guests <= CAPACITY)
                {
                    num_families++;
                }
    
                else
                {
                    break;
                }
            }
        }
        return num_families;
    }
    As is, this results in 7 families being invited and 24 family members. It's supposed to be 8 families and 26 family members. Again, FAMILIES_KNOWN is 10 and CAPACITY is 30.
    Last edited by shukiren; 11-23-2011 at 08:45 PM.

  10. #10
    Registered User
    Join Date
    Sep 2011
    Posts
    81
    Got it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Replies: 16
    Last Post: 08-25-2008, 11:08 PM
  3. sort linked list using BST
    By Micko in forum C Programming
    Replies: 8
    Last Post: 10-04-2004, 02:04 PM
  4. how do u sort a list of names?
    By CwannaB in forum C++ Programming
    Replies: 2
    Last Post: 03-04-2003, 04:19 PM
  5. Sort linked list
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 01-28-2002, 04:32 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21