0

For a class I have to use a recursive function to quicksort a linked list. This is on Lunix. This is my quicksort function, but it is causing a Segmentation fault. After some googling that means I have a pointer pointing to something it isn't allowed to, but I am not sure what I am doing wrong. I am not a new programmer, but I just started C a month ago so pointers are still a little confusing to me. Here is the function:

#include <stdlib.h>
#include <stdio.h>
#include "node.h"

//quicksort method
//takes one node pointer and recursively sorts in ascending order, returning the head node
struct mynode* quicksort(struct mynode *head)
{

int pivot = head->value;
struct mynode *current, *left, *right, *l_current, *r_current;
left = (struct mynode *)malloc(sizeof(struct mynode));
right = (struct mynode *)malloc(sizeof(struct mynode));
l_current = left;
r_current = right;

for (current=head; current; current=current->next) {
    if (current->value < pivot) {
        l_current->value = current->value;
        l_current->next = (struct mynode *)malloc(sizeof(struct mynode));
        l_current = l_current->next;
    } else {
        r_current->value = current->value;
        r_current->next = (struct mynode *)malloc(sizeof(struct mynode));
        r_current = r_current->next;
    }
}

left = quicksort(left);
right = quicksort(right);

for (current=left; current; current=current->next) {    
}

current->next = right;
return left;
}

Thanks for the help.

dohertyj08
  • 1
  • 1
  • 1
    run it under a debugger - you didnt say what platform. if lihux you need gdb – pm100 Feb 04 '15 at 22:30
  • 2
    `for (current=left; current; current=current->next) { } current->next = right;` : `(NULL)->next=right` – BLUEPIXY Feb 04 '15 at 22:31
  • `left = (struct mynode *)malloc(sizeof(struct mynode));` why do you allocate two nodes here? Also the malloc()d objects are uninitialised. – wildplasser Feb 04 '15 at 22:31
  • [Please don't cast the result of `malloc()`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc/605858#605858). – Quentin Feb 04 '15 at 22:56
  • qsort normally does not need any malloc operations, unless one malloc to be used during the swapping of data entries.. it does need a comparison function, and several passed in parameters that indicate things like length of each entry, how many entries, address of the data to sort, etc. the code is implementing a recursive qsort. This will be slower, take more memory, and be orders of magnitude more difficult to debug than a non recursive implementation. – user3629249 Feb 04 '15 at 23:08
  • if you use a debugger, then when the the seg fault event occurs, you can display the stack chain to determine exactly where the seg fault occurred and the current state of the pointers, etc when the seg fault occurred. – user3629249 Feb 04 '15 at 23:13
  • `gcc -Wall -Werror -g main.c && gdb ./a.out`, then `c` – Jonathon Reinhart Feb 05 '15 at 02:30
  • @Quentin I sometimes wonder if you're the dont-cast-malloc bot :-) – Jonathon Reinhart Feb 05 '15 at 02:31
  • @JonathonReinhart there should definitely be one. Or we need an army. – Quentin Feb 05 '15 at 02:36

0 Answers0