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.

#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 **);
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");

printf("final list = \n");

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)
{

if ( l1 == NULL )
return l2;
else
{
while ( l1->next )
l1 = l1->next;

l1->next = l2;

}
}

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

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;

}
}

/* 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 */
{

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

}

/* print out the whole linked list */
{
int i=0;

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

if ( i == 0 )
}

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

/* store the head pointer */

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

printf("\npivot = \n");

/* 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 */
/* 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);

/* 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);

/* 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");
printf("\n");
printf("\n");

fflush(stdin);
getchar();
}

printf("Final Summary\n");
printf("\n");
printf("\n");

}

/* 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;
}

###### Who is Participating?

Commented:
that's what i deduced from the code at the other link.
i did not try.
0

Author Commented:
or anyone has got sample programs to show?
so I can have that as a reference.

thanks a lot.
0

Software ArchitectCommented:
Hi ee_guest,
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20383052.html
Good luck,
Jaime.
0

Author 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

Software ArchitectCommented:
0

Author Commented:
jamie,
may i know what sort sganta is offerring in http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_10049950.html
0

Commented:
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 Commented:
0

Software 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

Author 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;

list = insert(list, 1);
list = insert(list, 3);
list = insert(list, 2);

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

while ( head != NULL )
{
}

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
{
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;

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 Commented:
i only managed to print out the first character after sorting.
0

Author Commented:
and the function is not sorting :(
0

Commented:
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

Software 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.