11

Problem: Trying to sort an array coming from a typedef struct I created (phonebook).

Goal: Trying to build a phonebook that allows users to add, delete, sort, and print the phonebook.

Where I'm at: I've got everything working except the sort. I've cobbled together a sort function from reading various web forums/examples, but can't get it to work.

Issue I'm having: After adding entries (which works fine), if you try to sort entries, the function zeroes out values of those entries and when you print the phonebook, it shows all entries as blank. It should sort them alphabetically by last name.

Here's the sort algorithm I have in place:

void Sort (phone phonebook[])
{
    phone temp;
    int i;  int j;

    for (i=0; i<19; i++)
    {
        for (j=i+1; j<19; j++)
        {
            if (strcmp(phonebook[i].Surname, phonebook[j].Surname) > 0)
            {
                temp=phonebook[i];
                phonebook[i]=phonebook[j];
                phonebook[j]=temp;

            }
        }
    }
}

Any ideas?


Full code here:

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

//typedef struct to define what's in the phonebook
typedef struct PhoneBookContacts
{
    char Name[20];
    char Surname[20];
    char PhoneNumber[20];
} phone;

//Function prototypes
void AddEntry (phone[]);
void DeleteEntry (phone[]);
void PrintEntry (phone[]);
void Sort (phone[]);
int counter = 0; //Global counter variable used to keep track of number of contacts

//Begin main function
int main (void)
{
    phone phonebook[20]; //Phonebook instance
    char userChoice; //Variable to use to select menu choice

    while (userChoice != 'Q') {
        printf ("***************\n");
        printf ("Please enter a command:\n");
        printf("'A': Add an entry\n");
        printf("'D': Delete an entry\n");
        printf("'S': Sort entries\n");
        printf("'P': Print the phonebook\n");
        printf("'Q': Quit\n");
        printf ("***************\n");

        scanf("%s", &userChoice);  //Stores menu choice into variable userChoice

        // Add Contact
        if (userChoice == 'A')
            AddEntry(phonebook);

        //Remove Contact
        if (userChoice == 'D')
            DeleteEntry (phonebook);

        //Print Contacts
        if (userChoice == 'P')
            PrintEntry(phonebook);

        //Sort Contacts
        if (userChoice == 'S')
            Sort(phonebook);

        //Quit
        if (userChoice == 'Q') {
            printf("Phonebook will now quit.");
            return 0;
        }
    }
}

//Function Definition to Add Contacts to the Phonebook
void AddEntry (phone phonebook[]) {
    counter++; //global counter increase

    printf("\nFirst Name: ");
    scanf("%s", phonebook[counter-1].Name); //counter-1 b/c arrays start at 0

    printf("Last Name: ");
    scanf("%s", phonebook[counter-1].Surname);

    printf("Phone Number (XXX-XXX-XXXX): ");
    scanf("%s", phonebook[counter-1].PhoneNumber);

    printf("\n%s added to phonebook\n", phonebook[counter-1].Name); //tell user friend added
}

void DeleteEntry (phone phonebook[])
{
    int x = 0;
    char deleteName[20];  // Temp string to compare to existing phonebook
    char deleteSurname[20];  //temp string
    char nullStr[20] = {"\0"};  // empty string to remove phonenumber

    printf("\nEnter name: ");
    scanf("%s", deleteName); //place into temp string
    printf("Enter Surname: ");
    scanf("%s", deleteSurname); //place into temp string

    for (x = 0; x < counter; x++)
    {
        if (strcmp(deleteName, phonebook[x].Name) == 0) //compare deleteName to phonebook.Name
        {
            for (x = 0; x < counter; x++)
            {
                if (strcmp(deleteSurname, phonebook[x].Surname) == 0) //If deleteSurname matches phonebook.Surname
                {
                    strcpy(phonebook[x].Name, nullStr); //Put null into Name
                    strcpy(phonebook[x].Surname, nullStr); //Null into Surname
                    strcpy(phonebook[x].PhoneNumber, nullStr); //Null into PhoneNumber
                    printf("Contact removed from phonebook.\n");
                    counter--;
                    break;
                }
            }

        }
        else printf("Invalid entry--try again.\n");
    }
}

// Function def to print contacts
void PrintEntry (phone phonebook[]) {
    int x = 0;
    printf("\nPhonebook entries:\n");

    for ( x = 0; x < counter; x++) {
        printf("\n(%d)\n", x+1); //Show contact number
        printf("Name: %s %s\n", phonebook[x].Name, phonebook[x].Surname); //Name
        printf("Number: %s\n", phonebook[x].PhoneNumber); //Number
    }
}

void Sort (phone phonebook[]) {
    phone temp;
    int i;  int j;

    for (i=0; i<19; i++) {
        for (j=i+1; j<19; j++) {
            if (strcmp(phonebook[i].Surname, phonebook[j].Surname) > 0) {
                temp=phonebook[i];
                phonebook[i]=phonebook[j];
                phonebook[j]=temp;
            }
        }
    }
}
6
  • 3
    +1 for a very well organized question. :)
    – Mysticial
    Oct 27, 2011 at 5:12
  • 1
    This doesn't solve your problem, but you should really look at using radix sort instead of bubble sort (unless you have memory allocation issues). It's quite a bit faster - Average case performance - Radix O(n) vs. BubbleSort O(n^2).
    – user849425
    Oct 27, 2011 at 5:17
  • 1
    @Michael He is sorting by an string field; radix sort fits only when sorting integers.
    – vz0
    Oct 27, 2011 at 5:18
  • "A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers." - Wikipedia
    – user849425
    Oct 27, 2011 at 5:19
  • .. or use quicksort which is O(n log n) which is proven to the the fasted any sorting can be, and it comes with the C-library so you don't have to write it
    – Soren
    Oct 27, 2011 at 5:21

3 Answers 3

6

You can use the already implemented sorting function qsort function available at stdlib.h:

int SortFunc(void* a, void* b) {
    phone *p1 = (phone*)a;
    phone *p2 = (phone*)b;

    return strcmp(p1->Surname, p2->Surname);
}

void Sort (phone phonebook[]) {
    qsort(phonebook, counter, sizeof(phone), &SortFunc);
} 

The function is usually Quicksort, but that's up to the C library implementation to decide.

Update:

The blank listing is because the sorting is reversed and always sorting all the 19 items of the phonebook, comparing the empty ones against the real ones. If you have less than 19 entries on the phonebook, the actual data is going to be present at the end of the phonebook array.

Your original Sort function was always working almost OK. Just change the end condition on the two for.

void Sort (phone phonebook[]) {
    phone temp;
    int i;  int j;

    for (i=0; i<counter; i++) {
        for (j=i+1; j<counter; j++) {
            if (strcmp(phonebook[i].Surname, phonebook[j].Surname) > 0) {
                temp=phonebook[i];
                phonebook[i]=phonebook[j];
                phonebook[j]=temp;
            }
        }
    }
}

I've also updated my Sort above.

6
  • 2
    Activating pedantic mode: qsort is not required to be quicksort.
    – paxdiablo
    Oct 27, 2011 at 5:23
  • vz0, I implemented your sort, and now instead of being blank, the values simply won't sort---i.e. when I print them, they are in the same order as before. I had my bubble sort algorithm do the same thing at one point (had it where I thought it should work, but elements still didn't print as expected). I might have a bug elsewhere? Hmm. Anyhow, thx for your answer and to the others contributing.
    – Josh T
    Oct 27, 2011 at 5:28
  • @JoshT There were a typo in my first answer. Check the parameters of the srtrcmp() call on SortFunc.
    – vz0
    Oct 27, 2011 at 5:30
  • corrected pone to phone and I'm compiling, but entries are blank now. back to square 1. :-|
    – Josh T
    Oct 27, 2011 at 5:40
  • 1
    @JoshT Nice, your original sort was OK! I've updated again. Hope this is for real :)
    – vz0
    Oct 27, 2011 at 5:47
1

First things first, you have a buffer overflow issue here:

char userChoice;
:
scanf("%s", &userChoice);

That scanf will write two bytes when you enter one character (the character plus a null terminator). This corrupted the first name of the first phonebook entry in my environment but, since it's undefined behaviour, it could do anything!

You can get around this by using:

char userChoice[] = "something that's not Q";
: 
scanf("%s", userChoice);
:
if (*userChoice == 'A')  // for all of these.

That won't stop a buffer overflow if you enter enough text but it will if you limit yourself to single character commands. If you want a truly robust user input function, see here.


Now to your specific problem. It looks like you have a bit of a bubble sort going on there, but your logic is slightly off. Assuming you don't want to use qsort (which would be the better way for real code), you just need to fix up a couple of things.

Your outer loop is okay, as is your inner loop, but the inner loop body should be comparing elements j and j+1, not j and i. That's because it works by swapping adjacent elements if they're out of order.

In addition, a forward focused bubble sort will place the highest element at the end of the list on the first pass, so you can't start j at i+1 on the second pass, simply because the first element may not be correct yet.

The following psuedo-code is your classic bubble sort:

didSwap = true
while didSwap:
    didSwap = false
    for i = 0 to lastidx - 1:
        if array[i] > array[i+1]:
            temp = array[i]
            array[i] = array[i+1]
            array[i+1] = temp
            didSwap = true

Read that, understand how it works, then implement it on your own. If you have trouble with that, I've included a working version below:

void Sort (phone phonebook[]) {
    phone temp;
    int i;  int didSwap;

    didSwap = 1;
    while (didSwap) {
        didSwap = 0;
        for (i = 0; i < counter - 1; i++) {
            if (strcmp(phonebook[i].Surname, phonebook[i+1].Surname) > 0) {
                temp=phonebook[i];
                phonebook[i]=phonebook[i+1];
                phonebook[i+1]=temp;
                didSwap = 1;
            }
        }
    }
}
0
for (i=0; i<19; i++)
{ 
    for (j=i+1; j<19; j++)

    {
        if (strcmp(phonebook[i].Surname, phonebook[j].Surname) > 0)
        {
            temp=phonebook[i];
            phonebook[i]=phonebook[j];
            phonebook[j]=temp;

        }

    }
}

Three problems with your code. First is the logic of your algorithm. Bubble sort works by fixing the order of two adjacent element. In your code, after the first iteration of your inner for loop, it's not going to compare two adjacent elements.

The second problem, again in sorting algorithm, your counters i and j are both going to 19, even when there is less entries than that. This might mess up the sorting as they will be reading invalid(uninitialized) entry. you should check the upper bound for the counter.

The next one is in the deletion

    if (strcmp(deleteName, phonebook[x].Name) == 0) //compare deleteName to phonebook.Name 
    {
        for (x = 0; x < counter; x++)
        {
            if (strcmp(deleteSurname, phonebook[x].Surname) == 0) //If deleteSurname matches phonebook.Surname
            {
                strcpy(phonebook[x].Name, nullStr); //Put null into Name
                strcpy(phonebook[x].Surname, nullStr); //Null into Surname
                strcpy(phonebook[x].PhoneNumber, nullStr); //Null into PhoneNumber
                printf("Contact removed from phonebook.\n");
                counter--;
                break;
            }

        }

    }

The code above will not check properly whether the first and last name since you're checking them separately. You only need one for loop with if( strcmp(deleteSurname, phonebook[x].Surname) == 0 && strcmp(deleteName, phonebook[x].Name) == 0 )

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.