0

I need to print a linked list in order but I need it to be sorted in a weird way and I couldnt find an answer. So I need it to be sorted first by the integer data(obviously bigger comes first), then within that I need it to be sorted by word. So lets say two nodes have the same data integer, then they would be sorted lexicographically by the word. The linked list is like this

struct node {
    int data;
    char word[125];
    struct node* next;
}

Any suggestions? It doesn't necessarily have to be sorted, I just have to print them in sorted order

11
  • 1
    How many nodes will you be processing? That is, any time complexity requirements? Commented Mar 29, 2017 at 22:44
  • 1
    There is a semicolon missing after your struct definition. #thedevilisinthedetail Commented Mar 29, 2017 at 22:44
  • 1
    You could apply basically any sorting algorithm here, but when you compare two nodes, just perform the word comparison if the two data are equal. Commented Mar 29, 2017 at 22:49
  • 2
    You could try converting the linked list to an array (find the length, create an array of nodes, and go through each element and set it) and then use qsort and convert it back. Commented Mar 29, 2017 at 22:54
  • 1
    The advantage of qsort() is that it has the sorting organized; you just have to write a comparison function (also called a comparator). Your comparator might look like: int cmp_node(const void *v1, const void *v2) { const struct node *np1 = *(node **)v1; const struct node *np2 = *(node **)v2; if (np1->data < np2->data) return -1; else if (np1->data > np2->data) return +1; else return strcmp(np1->word, np2->word); }. I'm assuming you end up with an array of node pointers, not an array of node structures. You end up with one less level of indirection if you sort an array of nodes. Commented Mar 29, 2017 at 23:01

1 Answer 1

1

Since you're only processing so few elements, you could just fit the whole list into an array, then sort it with qsort. Here's a quick example. Be careful not to overflow the nodes array in print_sorted - for such few nodes, you could just go through the linked list once to get the size, then malloc the space you need.

Notice that in the example, node_compare works with an array of pointers to node. If you want to work directly with an array of nodes, just remove the dereferences at the start of the function and cast them to const struct node * instead of const struct node **.

// for qsort
#include <stdlib.h>
// for strcmp
#include <string.h>

struct node {
    int data;
    char word[125];
    struct node* next;
};

int node_compare(const void *a, const void *b) {
    const struct node *first = *(const struct node **) a;
    const struct node *second = *(const struct node **) b;

    // Order nodes with same data alphabetically
    if (first->data == second->data) {
        return strcmp(first->word, second->word);
    } else {
        return first->data - second->data;
    }
}

void print_sorted(struct node *list) {
    struct node *nodes[512];

    // gather whole list into the array
    struct node *current = list;
    int arrayIndex = 0;
    while (current != NULL) {
        nodes[arrayIndex++] = current;
        current = current->next;
    }

    // sort the array
    qsort(nodes, arrayIndex, sizeof(struct node *), node_compare);

    // print em
    for (int i = 0; i < arrayIndex; i++) {
        printf("data: %d, word: %s\n", nodes[i]->data, nodes[i]->word);
    }
}

int main() {
    struct node a = { .data = 3, .word = "ayy", .next = NULL };
    struct node b = { .data = 3, .word = "zzz", .next = &a };
    struct node c = { .data = 3, .word = "ddd", .next = &b };
    struct node d = { .data = 10, .word = "toaster", .next = &c };
    struct node e = { .data = 0, .word = "box", .next = &d };

    print_sorted(&e);
    return 0;
}

This prints out:

data: 0, word: box
data: 3, word: ayy
data: 3, word: ddd
data: 3, word: zzz
data: 10, word: toaster

If you want descending order, change the bottom part of node_compare() to the following:

if (first->data == second->data) {
    return strcmp(second->word, first->word);
} else {
    return second->data - first->data;
}
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.