oster@ucblapis.berkeley.edu (David Phillip Oster) (03/28/86)
In article <402@mips.UUCP> hansen@mips.UUCP (Craig Hansen) writes: >There's a simpler way, using a merge sort instead of a heap sort. >The code below is O(n log n), and relies only on singly linked >be fairly simple to translate. The basic idea is to take the >list as pairs, sorting each pair, then take pairs of sorted >pairs and merge them together, so so on, taking geometrically >increasing-sized lists, until you have a single sorted list. >Craig Hansen >MIPS Computer Systems >...decwrl!glacier!mips!hansen > for ... > while ... > i := i - 1; > trailer := point; > point := point^.next; > end {while}; > if sublist[j] <> nil then trailer^.next := nil; > end {for}; Sorry guys, this is a stupid way to sort a list. Although your comaprison function is called O(n log n), the above code is executed n^2 times. It just blows the time codt to hell. I sort my lists by copying them into an array, sorting the array using qsort, then copying back to a list. --- David Phillip Oster ----------------------- ``What do you look like when you aren't visualizing?'' Arpa: oster@lapis.berkeley.edu Uucp: ucbvax!ucblapis!oster
hansen@mips.UUCP (Craig Hansen) (03/31/86)
> In article <402@mips.UUCP> hansen@mips.UUCP (Craig Hansen) writes: > >There's a simpler way, using a merge sort instead of a heap sort. > >The code below is O(n log n), and relies only on singly linked > >be fairly simple to translate. The basic idea is to take the > >list as pairs, sorting each pair, then take pairs of sorted > >pairs and merge them together, so so on, taking geometrically > >increasing-sized lists, until you have a single sorted list. > >Craig Hansen > >MIPS Computer Systems > >...decwrl!glacier!mips!hansen > > for ... > > while ... > > i := i - 1; > > trailer := point; > > point := point^.next; > > end {while}; > > if sublist[j] <> nil then trailer^.next := nil; > > end {for}; > > Sorry guys, this is a stupid way to sort a list. Although your comaprison > function is called O(n log n), the above code is executed n^2 times. It > just blows the time codt to hell. I sort my lists by copying them into an > array, sorting the array using qsort, then copying back to a list. > > --- David Phillip Oster > ----------------------- ``What do you look like when you aren't visualizing?'' > Arpa: oster@lapis.berkeley.edu > Uucp: ucbvax!ucblapis!oster David, you can sort your lists anyway stupid way you god-damn please. ~==~ The code you excerpt above is NOT executed n^2 times, it's executed O(n log n) times. Try profiling it if you can't reason it out. To explain further, the outer-most loop is executed O(log n) times: MergeLength := 1; while MergeLength < SymbolCount do begin ... MergeLength := MergeLength * 2; end {while}; The inner loop is order n; even though it is composed of nested loops: point := table; while point <> nil do begin ... end {while}; executes n/MergeLength times, and the loop: i := MergeLength; while (point <> nil) and (i > 0) do begin i := i - 1; ... end {while}; executes MergeLength times; the end result is O(n). Another way of seeing this is by noting that the inner loop moves "point" through the list exactly once. Did I lose anybody? -- Craig Hansen | "Evahthun' tastes MIPS Computer Systems | bettah when it ...decwrl!mips!hansen | sits on a RISC"
michaelo@tektronix.UUCP (Michael O'Hair) (04/05/86)
[ superstitousnonsense ] The simplest method I've found is to get the data into the linked list, "inlist"; pour "inlist" through a binary tree sort to "outlist". Easy to write, easy to read, easy to maintain, but keeps the stack pretty busy. Has any one got any figures, calculated or timed, on this method? Disclaimer: It's not TEK's fault, they only pay me. Michael O'Hair Tektronix, Inc. tektronix!tekgen!michaelo
levison@qucis.UUCP (Mike Levison) (04/11/86)
An algorithm for sorting items stored in linked lists will
be found in:
Motzkin, D. "A Stable Quicksort", Software: Practice
and Experience, Vol. 11, pp 607-611, 1981.
As the title suggests, the algorithm is basically Quicksort,
but with a different partition step, in which the list is
scanned sequentially from its beginning to its original end,
and items greater than the pivot are unlinked and attached
to the end.