Shamveel Ahammed Shamveel Ahammed - 20 days ago 9
C Question

Alphabetically sort in Linked Lists in C?

I am trying to sort the names in this linked list alphabetically but I not sure which would be a right approach to take. I created a method to compare the names in the list and update my current pointer each time. I keep getting errors. Could anyone suggest a better way to sort through the names? I am new to C and I am struggling to find a better way to implement this. Any help would be massively appreciated.

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

#define HOW_MANY 7

char *names[HOW_MANY] = { "Ben", "Chris", "RDJ", "Mark", "Scarlet", "Samuel", "Tom" };
int ages[HOW_MANY] = { 22, 24, 50, 26, 18, 32, 24 };

/* declare your struct for a person here */
struct person {
char *name;
int age;
struct person *next;
};

static struct person *compare_people(struct person *headptr, struct person *headptr) {
int didSwap = 1, limit = HOW_MANY - 1;
struct person *temp;
struct person *previous = headptr;
struct person *new = headptr -> next;

while (didSwap) {
didSwap = 0;
for (int i = 0; i < limit; i++) {
if (strcmp(previous->name, new->name) > 0) {
temp = previous;
previous = new;
new = temp;
didSwap = 1;
}
}
limit--;
}
return temp;
}

static struct person *insert_sorted(struct person *headptr, char *name, int age) {
struct person *ptr;
// Allocate heap space for a record
ptr = malloc(sizeof(struct person));
if (ptr == NULL)
abort();
// Assign to structure fields
ptr->name = name;
ptr->age = age;
ptr->next = NULL;

if (headptr == NULL) {
ptr->next = headptr;
headptr = ptr;
} else {
struct person *currptr = headptr;

while (currptr != NULL) {
currptr = compare_people(headptr, headptr);
}
headptr = currptr;
}
return headptr;
}

int main(int argc, char **argv) {
// initialise the pointer to be empty
struct person *headptr = NULL;

// To insert all the info in the array
for (int i = 0; i < HOW_MANY ; i++) {
headptr = insert_sorted(headptr, names[i], ages[i]);
}

struct person *current = headptr;
while (current != NULL) {
printf("The person's name is %s and the age is %d.\n", current->name, current->age);
current = current->next;
}
return 0;
}

Answer

Your approach is too complicated: the comparison function performs some kind of sorting and the insert function too. The comparison function should return an int whose value would be negative, 0 or positive, like strcmp(), and the insert_sorted should insert the new person into the list at the appropriate position using a simple iterative method.

Here is a simpler version:

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

#define HOW_MANY  7

char *names[HOW_MANY] = { "Ben", "Chris", "RDJ", "Mark", "Scarlet", "Samuel", "Tom" };
int ages[HOW_MANY] = { 22, 24, 50, 26, 18, 32, 24 };

/* declare your struct for a person here */
struct person {
    char *name;
    int age;
    struct person *next;
};

static int compare_people(const struct person *a, const struct person *b) {
     return strcmp(a->name, b->name);
}

static struct person *insert_sorted(struct person *headptr, char *name, int age) {
    // Allocate heap space for a record
    struct person *ptr = malloc(sizeof(struct person));
    if (ptr == NULL) {
        abort();
    }

    // Assign to structure fields
    ptr->name = name;
    ptr->age = age;
    ptr->next = NULL;

    struct person **pp = &headptr;
    while (*pp != NULL && compare_people(ptr, *pp) > 0) {
        pp = &(*pp)->next;
    }
    ptr->next = *pp;
    *pp = ptr;

    return headptr;
}

int main(int argc, char **argv) {
    // initialise the list to be empty
    struct person *headptr = NULL;

    // To insert all the info in the array
    for (int i = 0; i < HOW_MANY; i++) {
        headptr = insert_sorted(headptr, names[i], ages[i]);
    }

    struct person *current = headptr;
    while (current != NULL) {
        printf("The person's name is %s and the age is %d.\n", current->name, current->age);
        current = current->next;
    }
    return 0;
}
Comments