Selection sort with linked list's

Question

I have the following data structure:

struct scoreentry_node {
    struct scoreentry_node *next;
    int score;
    char name[1];    
};  
typedef struct scoreentry_node *score_entry;

I am trying to create a function that consumes my structure in order and arranges them in ascending order based on the name. I want to modify the input without allocating any memory or freeing anything:

I've tried your suggestions:

void selectionsort(score_entry *a) {
    for (; *a != NULL; *a = (*a)->next) {
        score_entry *minafteri = a;
        // find position of minimal element
        for (score_entry j = (*a)->next; j != NULL; j = j->next) {
            if (strcmp(j->name, (*minafteri)->name) == -1) {
                *minafteri = j;
            }
        }
        // swap minimal element to front
        score_entry tmp = *a;
        a = minafteri;
        *minafteri = tmp;
    }
}

I'm testing the above code with the following:

score_entry x = add(8, "bob", (add( 8 , "jill", (add (2, "alfred", NULL)))));
iprint("",x);
selectionsort(&x);
iprint("", x);
clear(x); //Frees the whole list

iprint() prints the score and name fields in the struct. My add function is as follows:

score_entry add(int in, char *n, score_entry en) {      
   score_entry r = malloc(sizeof(struct scoreentry_node) + strlen(n));
   r->score = in;
   strcpy(r->name, n);
   r->next = en;  
   return r;   
}

I'm getting heap errors and my second print doesn't print the sorted list, it prints nothing. What am I doing wrong, and what can I do to fix it?

Selection sort is a bad sorting algorithm for singly-linked lists (or lists in general, for that matter). If you're looking for a sorting algorithm that is both optimal in runtime and doesn't allocate any memory, try mergesort. — Philip, Mar 29 '12 at 06:15
`char name[1];` is a bit small. For the string to be null-terminated, the only valid string would be "", which would make comparing the names rather useless. — wildplasser, Mar 29 '12 at 10:42
@Philip for merge sort won't i need two list's ? i only have one .. — Thatdude1, Mar 29 '12 at 15:21
The "struct hack" is defining a `char name[1];` as the last struct element, but actually allocating more space (than 1 char) and trusting that the compiler will not limit your access to the thing to the size in the definition. Before c99 this was illegal (but often allowed by the implementation), with c99 came the VLA. — wildplasser, Mar 29 '12 at 16:48
Could be, could be not (behaviour is still undefined). You probably you made a trivial error somewhere. I won't look into it (because I think that selection sort on a linked list is the wrong thing to do, and I don't like hiding pointers behind typedefs) — wildplasser, Mar 29 '12 at 17:00
@wildplasser im trying mergesort, but im not sure how to split up my inputted list into 2 list's ? — Thatdude1, Mar 29 '12 at 17:51
here: http://stackoverflow.com/questions/9624467/complexity-of-mergesort-with-linked-list/9634059#9634059 is a split + merge sort I posted in another topic. — wildplasser, Mar 29 '12 at 18:12

keety · Answer 1 · 2012-03-29T07:05:55.963

1

besides passing the pointer by address (see comments below) you also need to fix the way you swap elements too

void selectionsort(score_entry *a) {
  for (; *a != NULL; *a = (*a)->next) 
  {
     score_entry *minafteri = a;
     // find position of minimal element
     for (score_entry j = (*a)->next; j != NULL; j = j->next) {
       if (strcmp(j->name, (*minafteri)->name) == -1) {
         *minafteri = j;
       }
      }
     // swap minimal element to front
     score_entry tmp = *a;
     a = minafteri; // put the minimal node to current position
     tmp->next = (*a)->next ; //fix the links
     (*minafteri)->next=tmp; //fix the links
  }
}

edited Mar 29 '12 at 07:05

answered Mar 29 '12 at 06:39

keety

17,231
4
51
56

Note that pass by reference doesn't exist in C, strictly. You are passing a value (the pointer) and dereferencing the pointer. http://stackoverflow.com/questions/2229498/passing-by-reference-in-c"> – Chris Mar 29 '12 at 06:56
This solution is broken: `*a = (*a)->next` -> `a = &(*a)->next` and the list is still corrupted since you do not update the link from the previous node to the one you move. – chqrlie Aug 13 '17 at 19:18

autistic · Answer 2 · 2017-08-13T08:50:55.923

This code is hideous! Not only have you not provided us with all of the necessities to reproduce your problem (we can't compile this!), but you've hidden pointer abstractions behind typedef (also a nightmare for us). Generally speaking, one shouldn't even use linked lists in C anymore let alone sort them...

Nonetheless, there are two answers here.

*minafteri = j; found within your find loop actually modifies your list! Why should your find loop be modifying your list?

Answer: it shouldn't! By instead assigning minafteri = &j->next, you won't be modifying the list with your find loop...

Alternatively, you could perform the swap inside of that loop.

*minafteri = j; would need to swap the following, in this order:

(*minafteri)->next and j->next
*minafteri and j

Do you think that single line of code is capable of performing those two swaps? Well, it gets half way through one of them... and removes a heap of elements from your list in the process!

The following appears to be a faulty attempt swapping elements:

score_entry *minafteri = a; // half of assigning `a` to `a`
/* SNIP!
 * Nothing assigns to `minafteri`  in this snippet.
 * To assign to `minafteri` write something like `minafteri = fubar;` */
score_entry tmp = *a;       // half of assigning `*a` to `*a`
a = minafteri;              // rest of assigning `a` to `a`
*minafteri = tmp;           // rest of assigning `*a` to `*a`

It's really just assigning *a to *a and a to a... Do you think you need to do that?

I'd have thought you'd notice that when you were creating your MCVE... Ohh, wait a minute! Shame on you!

Focus on swapping two nodes within a list as a smaller task. Once you've done that, consider taking on this task.

score 0 · Answer 3 · answered Aug 13 '17 at 19:15

There are multiple problems in your code:

if (strcmp(j->name, (*minafteri)->name) == -1) { is incorrect: strcmp() does not necessarily return -1 when the first string is less than the second, it can return any negative value.
The way you adjust the links in order to move the lower entry is incorrect: you cannot update the link from the previous node to the one you move to the start. The list is corrupted.

Here is an improved version:

void selectionsort(score_entry *a) {
    for (; *a != NULL; a = &(*a)->next) {
        // find position of minimal element
        score_entry *least = a;
        for (score_entry *b = &(*a)->next; *b != NULL; b = &(*b)->next) {
            if (strcmp((*b)->name, (*least)->name) < 0) {
                least = b;
            }
        }
        if (least != a) {
            // swap minimal element to front
            score_entry n = *least;
            *least = n->next;   /* unlink node */
            n->next = *a;       /* insert node at start */
            *a = n;
        }
    }
}

score 0 · Answer 4 · answered Jan 01 '19 at 14:17

Here is the Java Implementation of Selection Sort on Linked List:

Time Complexity: O(n^2)

Space Complexity: O(1) - Selection sort is In-Place sorting algorithm

class Solution 
{
    public ListNode selectionSortList(ListNode head)
    {
        if(head != null)
        {
            swap(head, findMinimumNode(head));
            selectionSortList(head.next);
        }
        return head;
    }

    private void swap(ListNode x, ListNode y)
    {
        if(x != y)
        {
            int temp = x.val;
            x.val = y.val;
            y.val = temp;    
        }
    }

    private ListNode findMinimumNode(ListNode head)
    {
        if(head.next == null)
            return head;

        ListNode minimumNode = head;

        for(ListNode current = head.next; current != null; current = current.next)
        {
            if(minimumNode.val > current.val)
                minimumNode = current;
        }
        return minimumNode;
    }
}

This question is tagged C, not Java. – Blastfurnace Jan 01 '19 at 14:52 — Blastfurnace, Jan 01 '19 at 14:52

score 0 · Answer 5 · answered Mar 29 '12 at 06:13

0

You have to pass the argument to selectionsort by reference:

void selectionsort(score_entry *a) {
    for (; *a != NULL; *a = (*a)->next) 
    {
      score_entry *minafteri = a;
      // find position of minimal element
      for (score_entry j = (*a)->next; j != NULL; j = j->next) {
      if (strcmp(j->name, (*minafteri)->name) == -1) {
         *minafteri = j;
      }
    }
     // swap minimal element to front
      score_entry tmp = *a;
      a = minafteri;
      *minafteri = tmp;
  }
}

answered Mar 29 '12 at 06:13

Some programmer dude

400,186
35
402
621

Umm i have typedef struct scoreentry_node *score_entry; isn't it a pointer to the struct already ? – Thatdude1 Mar 29 '12 at 15:20
@Beginnernato Here you need to pass the reference to the pointer, so a pointer to a pointer. – Some programmer dude Mar 29 '12 at 15:29
So it would take in somethin like `selectionsort(&x)`; where x is a pointer a struct ? and i after i call selection sort, x would be sorted ? – Thatdude1 Mar 29 '12 at 15:48
editted questions, I'm having problems with the new `selection sort` – Thatdude1 Mar 29 '12 at 16:14
1

This solution is broken: `*a = (*a)->next` -> `a = &(*a)->next` and the list is still corrupted since you do not update the link from the previous node to the one you move. – chqrlie Aug 13 '17 at 19:20

Selection sort with linked list's

5 Answers5

Linked