quicksort linked list

I have got the below program to attempt to quick sort a linked list.
At the moment i have all the codes and am able to sort the first cycle where the left marker and right marker have crossed.
Now, I am faced with the problem as to where to place my recursive call.

Please help..



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

typedef struct node {
    struct node *next;
    int x;
} node_t;

int check_length(node_t *);
node_t *goto_nth_node(node_t *, int);
node_t *append_list(node_t *, node_t *);
node_t *append_node(node_t *, int);
node_t *create_node();
void free_list(node_t **);
void display_linked_list(node_t *);
void quicksort_linked_list(node_t **);
node_t *find_pivot(node_t *);

int main()
{
    node_t *list=NULL;

    list = create_node();
    list->x = 157;
    list = append_node(list, 243);
    list = append_node(list, 219);
    list = append_node(list, 351);
    list = append_node(list, 749);
    list = append_node(list, 109);
    list = append_node(list, 245);
    printf("Before\n");
    display_linked_list(list);

    quicksort_linked_list(&list);
    printf("final list = \n");
    display_linked_list(list);
   
    free_list(&list);
   
    return 0;
}

/* return the total number of nodes in a linked list */
int check_length(node_t *list)
{
    int count=0;
    while ( list != NULL )
    {
        list = list->next;
        count++;
    }

    return count;
}

/* go to the nth node as specified by integer n */
node_t *goto_nth_node(node_t *list, int n)
{
    int i;
    node_t *nth_pos_list;

    nth_pos_list = list;
    for ( i=1; i<n; i++ )
        nth_pos_list = nth_pos_list->next;

    return nth_pos_list;
}

/* append a linked list l2 to l1 */
node_t *append_list(node_t *l1, node_t *l2)
{
    node_t *head=l1;
   
    if ( l1 == NULL )
        return l2;
    else
    {
        while ( l1->next )
            l1 = l1->next;

        l1->next = l2;
       
        return head;
    }
}

/* append a node to existing node with 2nd parameter value */
node_t *append_node(node_t *list, int new_x)
{
    node_t *head;
    node_t *new_node=NULL;

    head = list;

    new_node = create_node();
    new_node->x = new_x;

    if ( list == NULL )
        return new_node;
    else
    {
        while ( list->next )
            list = list->next;

        list->next = new_node;

        return head;
    }
}

/* create and return a node for a linked list */
node_t *create_node()
{
    node_t *empty_node;

    if ( (empty_node = (node_t *)malloc(sizeof(node_t))) == NULL )
    {
        perror("Error: ");
        exit(1);
    }

    /* make it point to null */
    empty_node->next = NULL;

    /* return the empty node */
    return empty_node;
}

/* free every node in a linked list */
void free_list(node_t **list_head)
{
    node_t *x = *list_head;

    while ( x )
    {
        free(x);
        x = x->next;
    }

    *list_head = NULL;
}

/* print out the whole linked list */
void display_linked_list(node_t *list)
{
    int i=0;

    while ( list )
    {
        i++;
        printf("#%d = %d\n", i, list->x);
        list = list->next;
    }

    if ( i == 0 )
        printf("Linked list is empty\n");
}

/* quicksort a linked list in ascending order based on value of x */
void quicksort_linked_list(node_t **list)
{
    node_t *head=NULL;
    node_t *pivot=NULL;
    node_t *left=NULL;
    int left_position;
    node_t *right=NULL;
    int right_position;
    int temp;

    /* store the head pointer */
    head = *list;

    /* get the pivot pointer */
    pivot = find_pivot(*list);

    printf("\npivot = \n");
    display_linked_list(pivot);

    /* pivot is empty or pivot is only of 1 node */
    if ( pivot == NULL || pivot->next == NULL )
        return;

    while ( 1 )
    {
        /* get the left marker */
        /* we start from the left-most to just before pivot */
        /* left marker will be the pointer to the first node */
        /* with x-value more than or equal to pivot-value but if cannot find */
        /* it will be the pivot pointer */
        left = head;
        /* set left position to 1 that is first node */
        left_position = 1;
        while ( left != pivot )
        {
            if ( left->x >= pivot->x )
                break;
            else
            {
                /* increase left position */
                left_position++;
                left = left->next;
            }
        }
        printf("\nleft = %d\n", left_position);
        display_linked_list(left);

        /* get the right marker */
        /* we start from the right most and traverse to the left */
        /* right marker will be the first pointer found with x-value */
        /* less than the pivot value */
        /* get the right position and it will be the length for start */
        right_position = check_length(*list);
        right = goto_nth_node(*list, right_position);
        while ( right_position && right->x >= pivot->x  )
        {
            right_position--;
            if ( right_position > 0 )
                right = goto_nth_node(*list, right_position);
        }
        printf("\nright = %d\n", right_position);
        display_linked_list(right);

        /* markers not crossed so we swap left and right values */
        if ( left_position < right_position )
        {
            /* we swap left and right values */
            temp = right->x;
            right->x = left->x;
            left->x = temp;

            if ( left == pivot )
                pivot = right;
            else
                if ( right == pivot )
                    pivot = left;
        }
        /* markers have crossed */
        else
        {
            break;
        }
       
        printf("Summary\n");
        display_linked_list(pivot);
        printf("\n");
        display_linked_list(left);
        printf("\n");
        display_linked_list(right);

        fflush(stdin);
        getchar();
    }
   
    printf("Final Summary\n");
    display_linked_list(pivot);
    printf("\n");
    display_linked_list(left);
    printf("\n");
    display_linked_list(right);

}

/* find the pivot and return a pointer to the node */
node_t *find_pivot(node_t *list)
{
    int pivot_x_value;
    node_t *pivot=NULL;

    /* traverse the list to find the pivot */
    while ( list )
    {
        if ( pivot == NULL )
        {
            pivot_x_value = list->x;  /* set pivot x-value */
            pivot = list;               /* set pivot pointer */
        }
        else
        {
            /* pivot_x_value is less than the x value of current node of linked list */
            if ( pivot_x_value < list->x )
            {
                /* we set the new pivot_x_value and pivot pointer */
                pivot_x_value = list->x;
                pivot = list;
                break;
            }
        }

        /* move to next node */
        list = list->next;
    }

    return pivot;
}


ee_guestAsked:
Who is Participating?
 
hongjunConnect With a Mentor Commented:
that's what i deduced from the code at the other link.
i did not try.
0
 
ee_guestAuthor Commented:
or anyone has got sample programs to show?
so I can have that as a reference.

thanks a lot.
0
 
Jaime OlivaresSoftware ArchitectCommented:
Hi ee_guest,
Here is a previous question about this:
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20383052.html
Good luck,
Jaime.
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
ee_guestAuthor Commented:
Jamie,
    actually i saw that thread before but then i cannot seem to get that to work.. Do you mind piece them for me?
0
 
Jaime OlivaresSoftware ArchitectCommented:
0
 
ee_guestAuthor Commented:
jamie,
    may i know what sort sganta is offerring in http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_10049950.html
0
 
Harisha M GCommented:
Here is a simple sample function for QSort:

void qs(int A[], int lo, int up)
{
  int i;
  if(up>lo)
  {
    i = partition(A,lo,up);
    qs(A,lo,i-1);
    qs(A,i+1,up);
  }
}

int partition(int A[], int lo, int up)
{
  int i,p,q,t;
  p = lo;
  q = up + 1;
  i = A[lo];
  while(q>=p)
  {
    while(A[++p]<i);
    while(A[--q]>i);
    if(q>p)
    {
      t = A[p];
      A[p] = A[q];
      A[q] = t;
    }
  }

  t= lo;
  A[lo]= A[q];
  A[q] = t;
  return q;
}

You can call this function directly to sort :)
- MGH
0
 
ee_guestAuthor Commented:
linked list is required
0
 
Jaime OlivaresSoftware ArchitectCommented:
>jamie,
>    may i know what sort sganta is offerring in http://www.experts->exchange.com/Programming/Programming_Languages/C/Q_10049950.html

It appear to be a "selection sort", not so efficient.
0
 
ee_guestAuthor Commented:
hi..

this is what i got now but is not working..


#include <stdio.h>

typedef struct node {
    struct node *next;
    int item;
} node;

node *quicksort(node *l1);
void partition(node *l1, int p, node * low, node * high);
node * insert(node *list, int element);
node * append(node * L1, node * L2);

int main()
{
    node *list=NULL;
    node *head;
   
    list = insert(list, 1);
    head = list;
    list = insert(list, 3);
    list = insert(list, 2);

    while ( list )
    {
        printf("%d\n", list->item);
        list = list->next;
    }

    list = head;
    head = quicksort(list);
    while ( head != NULL )
    {
        printf("%d\n", head->item);
        head = head->next;
    }
    list = head;

    if ( list != NULL )
    {
        free(list);
        list = NULL;
    }

      return 0;
}

node *quicksort(node *l1)
{
    node *low = NULL;
      node *high = NULL;
    int p;
   
      if (l1 == NULL)  //if list is empty, return NULL
          return NULL;

      if(l1->next ==  NULL)  //if list has only one item,
          return l1;          
    else
    {
        //pivot element
        //make the pivot = first item
        p = l1->item;          

        //partition the list around p
        partition(l1,p,low,high);  

        //sort the low
        low = quicksort(low);      

        //sort the high
        high = quicksort(high);    
       
        //insert p in low
        low = insert(low,p);      

        //insert high in low
        l1 = append(low,high);    

        //return pointer to beginning of list
        return l1;                
    }                          

}

void partition(node *l1, int p, node * low, node *high)
{
      //point t to next item in list
      node *t = l1->next;  

    while(t != NULL)  //while the list isn't empty
    {
        if (t->item >= p)  //if item > pivot
        {
            /* add greater nums to list */
            high = insert(high, t->item);
        }
        else  
        {
            /* add low */
            low = insert(low, t->item);
        }
       
        t = t->next;
    }
}
      
node * insert(node *list, int element)  //creates the lists
{
    /* create new node with element as item */
    node *newnodeptr = (node*)malloc(sizeof(node));
    newnodeptr->item = element;
    newnodeptr->next = NULL;

    /* list is empty so add it to front */
    if(list ==  NULL)
        list= newnodeptr;
    else
    {
        /* go to end of list */
        node *temp = list;    
       
        while ( temp->next != NULL )
            temp= temp->next;

        /* add newnodeptr */
        temp->next = newnodeptr;  
    }

    return list;
}

node * append(node * L1, node * L2)
{
    node * retval = (node*)malloc(sizeof(node));
    retval=NULL;
   
    if ( L1 == NULL )
        retval = L2;
    else
    {
        L1->next = append(L1->next, L2);
        retval = L1;
    }
   
    return retval;
}



0
 
ee_guestAuthor Commented:
i only managed to print out the first character after sorting.
0
 
ee_guestAuthor Commented:
and the function is not sorting :(
0
 
hongjunCommented:
Change to the following

void partition(node *l1, int p, node **low, node **high);
...


void partition(node *l1, int p, node **low, node **high)
{
...
// all low and high to *low and *high
}


also when you call partition, you do this
partition(l1,p,&low,&high);  




hongjun
0
 
Jaime OlivaresSoftware ArchitectCommented:
Quicksort is not so recommended for linked list, becuase it need indexed (random) access to adquire pivot value, and that is not efficient in linked list, but for arrays. Even bubble sort is easier and cleaner to implement and have near performance than quicksort in linked lists, depending on specific order.
Have a look to this interesting document:
http://www.qucis.queensu.ca/home/cisc121/2002f/lecturenotes/mcleod/Fall121_Nov14_slides.pdf
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.