Solved

quicksort linked list

Posted on 2004-10-02
14
1,559 Views
Last Modified: 2013-12-14
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;
}


0
Comment
Question by:ee_guest
  • 7
  • 4
  • 2
  • +1
14 Comments
 

Author Comment

by:ee_guest
ID: 12208438
or anyone has got sample programs to show?
so I can have that as a reference.

thanks a lot.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12208545
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
 

Author Comment

by:ee_guest
ID: 12208556
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
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12208558
0
 

Author Comment

by:ee_guest
ID: 12208574
jamie,
    may i know what sort sganta is offerring in http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_10049950.html
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 12208639
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
 

Author Comment

by:ee_guest
ID: 12208647
linked list is required
0
Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12208662
>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
 

Author Comment

by:ee_guest
ID: 12208696
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
 

Author Comment

by:ee_guest
ID: 12208701
i only managed to print out the first character after sorting.
0
 

Author Comment

by:ee_guest
ID: 12208708
and the function is not sorting :(
0
 
LVL 33

Expert Comment

by:hongjun
ID: 12208742
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
 
LVL 33

Accepted Solution

by:
hongjun earned 500 total points
ID: 12208743
that's what i deduced from the code at the other link.
i did not try.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12208750
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

Featured Post

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org (http://seleniumhq.org) Go to that link and select download selenium in the right hand columnThat will then direct you to their downlo…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now