Solved

Posted on 2004-10-02
1,559 Views
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;
}

0
Question by:ee_guest
• 7
• 4
• 2
• +1

Author Comment

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

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

Author Comment

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

ID: 12208558
0

Author Comment

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

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

ID: 12208647
0

LVL 55

Expert Comment

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

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;

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 Comment

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

Author Comment

ID: 12208708
and the function is not sorting :(
0

LVL 33

Expert Comment

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

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

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

### Suggested Solutions

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.
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.