C Insertion Sort - Implementation

Question

I've just started programming in C and need a bit of help with my implementation of Insertion Sort.

I am doing a C list insertion sort.

Here is the peseudocode for it, which I want to convert into C

otherwise
use a loop to find the last item in the list which should precede the new person set the new person's "next" link to point to whatever follows this list item

set the "next" link of this item to point to the new person

return the (start of the) list

Here is my partial implementation of my pseudocode

else    
      {
         for (int i =0; i < HOW_MANY; i++) 
         {

        people = people -> next;
        if (people -> next == NULL) return people;
     } //for
      }//else

       return pointer;    
}

Here is my full method:

struct person *insert_sorted (struct person *people, char *name, int age) {
//create a new space for the new person
  struct person *pointer = malloc(sizeof(struct person));
   // check it succeeded
    if(pointer == NULL)
    { 
     printf("The program could not allocate memory ");
      exit(-1);
    }
     // set the data for the new person
      strcpy(pointer -> name, name);
      pointer -> age = age;
      pointer -> next = people;
     // if the current list is empty
      if (people == NULL)
      {
        // set the new person's "next" link to point to the current list"
    pointer -> next = people;
    // return a pointer to the new person
    return pointer;
      }
else    
      {
         for (int i =0; i < HOW_MANY; i++) 
         {

        people = people -> next;
        if (people -> next == NULL) return people;
     } //for
      }//else

       return pointer;    
}

If you need the full program coude, let me know.

Thank you!

Sarah :)

Answer 1

before inserting the element into the list *people you should check the the correct position. try this:

struct person *insert_sorted (struct person *people, char *name, int age) {

//create a new space for the new person
struct person *pointer = malloc(sizeof(struct person));
// check it succeeded
if(pointer == NULL)
{ 
 printf("The program could not allocate memory ");
  exit(-1);
}
 // set the data for the new person
  strcpy(pointer -> name, name);
  pointer -> age = age;
struct person *cursor = people;
struct person *previous = people;
if(people == NULL){
    pointer->next = NULL;
    return pointer;
}
while(cursor!=NULL && strcmp(pointer->name,cursor->name)<0){
    previous = cursor;
    cursor = cursor->next;
}
if(previous!=NULL)
    previous->next = pointer;
pointer->next = cursor;
return people;
}

in this way you insert the new element after the first element with a name alphabetically lower and you link it with the next element.

Answer 2

I've done nothing to this code beyond naming things correctly, eliminating redundant comments, and running it through indent -linux.

struct person *insert_sorted(struct person *people, char *name, int age)
{
        struct person *newperson = malloc(sizeof *newperson);
        if (newperson == NULL) {
                printf("The program could not allocate memory ");
                exit(-1);
        }

        strcpy(newperson->name, name);
        newperson->age = age;
        newperson->next = people;

        if (people == NULL) {
                newperson->next = people;
                return newperson;
        }

        for (int i = 0; i < HOW_MANY; i++) {
                people = people->next;
                if (people->next == NULL)
                        return people;
        }

        return newperson;
}

A couple of things pop out immediately:

• it's not clear that you'e initializing all of *newperson. Safest is newperson = calloc(1, sizeof *newperson), then readers don't even have to think about it, always a good result.

• you don't show the structure definition, but you're not checking whether the inbound name fits in the storage at newperson->name -- and if newperson->name is a pointer, you've allocated none for it at all.

• there's a redundant assignment to newperson->next, raising the opposite question, of whether there's something not apparent or perhaps missing that makes it necessary.

• I don't see where in here you're comparing key values.