From abe49@hotmail.com Tue, 1 Dec 1998 14:06:19 -0600 X-SystemInfo: Internet: EMail X-Message-No: 918 (database) From: abe49 To: boisvert Subject: Re: sorting chained strcutures - how? Date: Tue, 1 Dec 98 15:06:00 Message-ID: <199812012006.OAA15640@x14.dejanews.com> Reply-To: abe49@hotmail.com Return-Path: Received: from m1.dejanews.com (m1.dejanews.com [208.10.192.32])by mail.hotpop.com (8.9.1/8.9.1) with ESMTP id QAA09181for ; Tue, 1 Dec 1998 16:18:04 GMT X-Advertisement: --------------------------------------------Sent By HotPOP.com FREE Email Get your FREE POP email at www.HotPOP.com -------------------------------------------- Received: from x14.dejanews.com (ix14.dejanews.com [10.2.1.205])by m1.dejanews.com (8.8.5/8.8.5) with ESMTP id OAA18798for ; Tue, 1 Dec 1998 14:06:20 -0600 Received: (from www@dejanews.com)by x14.dejanews.com (8.7.6/8.6.12) id OAA15640; Tue, 1 Dec 1998 14:06:19 -0600 X-maf: Status: ------------------------------------------------------------------------------ This message was forwarded to you from Deja News by abe49@hotmail.com. Deja News, the discussion network, offers free web-based access to more than 50,000 high-quality discussion forums. Come and visit us on the web at http://www.dejanews.com/=zzz_maf/ ------------------------------------------------------------------------------ Sponsored by: Audio Book Club Join and get 4 bestselling audiobooks 1c http://www.audiobookclub.com/micro/home.asp?AID=S036L004B009 ------------------------------------------------------------------------------ (beginning of original message) Subject: Re: sorting chained strcutures - how? From: heinz@hwg.muc.de (Heinz Wrobel) Date: 1996/09/15 Newsgroups: comp.sys.amiga.programmer Reinhard Katzmann (Suamor@student.uni-tuebingen.de) wrote: > /* Sort the Array */ Hmm. If you use insertion sort, why are you using the backup array with those list pointers at all? You are working your way through the list sequentially, sorting in the "current" element at the "right" position. This means IMHO that you might as well walk the list directly to find the insertion point and use Exec List functions to remove and re-insert the node at the right position. You just have to stash the ln_Succ pointer before removing the current node. How about this as general insertion sort based approach? /*------------------------------------------------------------------------*/ /* * * $Id: sortminlist.c 1.1 1996/09/15 07:42:23 heinz Exp $ * */ /*------------------------------------------------------------------------*/ /*------------------------------------------------------------------------*/ /* * A simple Insertion Sort based MinList sort function with a test case * (C)1996 by Heinz Wrobel, * * Based on SAS/C 6.56. Use a command line like this to check this out: * SC $*.c LINK DEF=TEST */ /*------------------------------------------------------------------------*/ #include #include #define __USE_SYSBASE /* SAS/C magic */ #include /* SAS/C magic */ /*------------------------------------------------------------------------*/ void SortMinList(struct MinList *mlh, LONG cmpcallback(APTR mn1, APTR mn2)) { struct MinNode *mn1, *mn2, *mnnext; /* We are doing a simple insertion like sort here, working our way * sequentially through the list. The runtime should be acceptable * for smaller lists. MinLists are used because this is the lowest * common denominator for all lists. I always felt that it is better * to cast something down than to cast it upwards. */ /* This makes sense only if we have more than one node in the list! */ mn1 = mlh->mlh_Head; if(mn1->mln_Succ) { /* While there is still a current node to sort in, sort it in. * We stash the next pointer right away to avoid losing it on * node removal. Note how we also skip the very first node! */ for(mn1 = mn1->mln_Succ; mnnext = mn1->mln_Succ; mn1 = mnnext) { /* Work our way backwards to find * the correct insertion point */ for(mn2 = mn1->mln_Pred; mn2->mln_Pred; mn2 = mn2->mln_Pred) { /* Our callback must return the same values * strcmp would return: * <0 : mn1 < mn2 * =0 : mn1 == mn2 * >0 : mn1 > mn2 * We stop when we find a node that is smaller than the * current one and insert our node after it */ if(cmpcallback(mn1, mn2) > 0) { break; } /* if */ } /* for */ /* Only do something, if we are not at * the correct position yet */ if(mn2->mln_Succ != mn1) { /* Remember how we stashed the next pointer to continue! */ Remove((struct Node *)mn1); Insert((struct List *)mlh, (struct Node *)mn1, (struct Node *)mn2); } /* if */ } /* while */ } /* if */ } /* SortMinList */ /*------------------------------------------------------------------------*/ #ifdef TEST #define USE_BUILTIN_MATH /* SAS/C magic. Not really needed */ #include #include #include LONG cmpcallback(struct Node *n1, struct Node *n2) { return(strcmp(n1->ln_Name, n2->ln_Name)); } /* cmpcallback */ int main(int argc, char **argv) { struct List lh; struct Node *n, *nextn; char buf[512]; /* Read lines from stdin and print them sorted to stdout */ NewList(&lh); while(fgets(buf, sizeof(buf) - 1 /* Paranoia */, stdin)) { n = (struct Node *)malloc(sizeof(struct Node) + strlen(buf) + 1); if(n) { n->ln_Name = (char *)(n + 1); strcpy(n->ln_Name, buf); AddTail(&lh, n); } /* if */ } /* while */ /* Now sort the list */ SortMinList((struct MinList *)&lh, cmpcallback); /* And finally print it */ for(n = lh.lh_Head; nextn = n->ln_Succ; n = nextn) { fputs(n->ln_Name, stdout); } /* for */ return(0); } /* main */ #endif /* TEST */ /*------------------------------------------------------------------------*/ /* EOT */ -- Heinz Wrobel Private Mail: heinz@hwg.muc.de My private FAX: +49 89 850 51 25, I prefer email (end of original message) ------------------------------------------------------------------------------ You can view this message and the related discussion by following this link: http://www.dejanews.com/=zzz_maf/dnquery.xp?search=thread&svcclass=dnserver&recnum=%3cheinz.1don@hwg.muc.de%3e%231/2 We hope to see you soon at Deja News, the discussion network. http://www.dejanews.com/=zzz_maf/