TF>>How do i (quick)sort linked lists?
TH>Collect the pointers into an array. Sort the pointers using whatever key
TH>you wish to sort by. Then build a new linked list. ___ Blue Wave/QWK
BG>I would recommend forgetting a quick sort, and just re-build a
BG>copy of the linked list in sorted form.
But, *how* do you sort it?
BG>The main nice feature about linked lists is the ability to insert
BG>items with the minimum of fuss.
True, but that has nothing to do with sorting. Whether its a linked
list, or an array - some sort of sorting algorithm will have to be
employed.
BG>Even better, sort the list stright away as you add items in.
BG>Insert them in the right place to start with. (That is, if it's
BG>appropiate to do so).
It's still sorting, and not very effient. The list will have to be
scanned for each insertion. Average efficiency would be N/2 for
insertion and deletion. I binary tree would be more effient, Big 'O'
would be log N for both ways.
___ Blue Wave/QWK v2.12
--- Maximus/2 3.01
---------------