Sorting array from typedef struct in C

Question

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;
            }
        }
    }
}

Answer 1

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.

Answer 2

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;
            }
        }
    }
}