On 4/27/06, Gene <[EMAIL PROTECTED]> wrote:
Lukas Šalkauskas wrote:
>
> oh thats!, maybe you can give me some examples? or maybe some links with good information about it.
You asked for the best way, not for code!
-----------------------------------------
#include <stdio.h>
typedef struct node { struct node *next; } *NODE, NODE_REC;
static int (*Cmp)();
/* Quicksort list h, append t at the end, and
deposit the result in *r. (The append
is done by induction.) */
static void q(NODE h, NODE t, NODE *r)
{
NODE p, lo, hi, next;
int nlo, nhi;
while (h != NULL) {
/* inductive case */
nlo = nhi = 0; lo = hi = NULL;
/* partition */
for (p = h->next; p != NULL; p = next) {
next = p->next;
if ((*Cmp)(p, h) < 0) {
p->next = lo; lo = p; ++nlo;
}
else {
p->next = hi; hi = p; ++nhi;
}
}
/* recur */
if (nlo < nhi) {
q(lo, h, r);
r = &h->next; h = hi; /* eliminated tail-recursive call */
}
else {
q(hi, t, &h->next);
t = h; h = lo; /* eliminated tail recursive call */
}
}
*r = t; /* base case */
}
/* Sort any singly linked list where the `next' pointer is the first
field
wrt predicate `cmp'. Uses O(lg n) stack and no other temp space. */
void lqsort(void *lstp, int (*cmp)())
{
NODE rtn;
Cmp = cmp;
q(*(void**)lstp, NULL, lstp);
}
/* Quick and dirty sort utility. */
typedef struct line {
struct line *next;
char text[1];
} *LINE, LINE_REC;
int cmp_lines(LINE l1, LINE l2)
{
return strcmp(l1->text, l2->text);
}
void main(void)
{
char buf[1000];
LINE lst, p;
void *malloc();
lst = NULL;
while (gets(buf) != NULL) {
p = malloc(sizeof(LINE_REC) + strlen(buf));
strcpy(p->text, buf);
p->next = lst; lst = p;
}
lqsort(&lst, cmp_lines);
for (p = lst; p != NULL; p = p->next)
puts(p->text);
}
--
You can contact me by IM or IRC too:
msn messanger: [EMAIL PROTECTED]
yahoo messanger: [EMAIL PROTECTED]
Google Talk: [EMAIL PROTECTED]
ICQ: 210963133
Skype: halfas.online.now
IRC: HalFas` (irc2.omnitel.net )
web: www.revidev.com
http://rvision.gamedev.lt/RVengine
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
