Re: the sort function in lisp (destructive)

* Gene <3d734438-8f14-48ab-95f6-46aec08e7249@xxxxxxxxxxxxxxxxxxxxxxxxxxx> :
Wrote on Sun, 6 Jan 2008 13:20:31 -0800 (PST):
|> > In fact looking at the source for Corman Lisp I discovered that it
|> > reads  the CAR into a vector, sorts that, and then puts the values
|> > back in the  CAR's in sorted order.
|>
|> This might have been done for other reasons than avoiding side-effect.
|> For example, to avoid having two different sort algorithms, or even
|> because it didn't occur to him how to write the algorithm without
|> doing indexed access.
|>
| Another possible reason is to avoid a certain kind of degenerate cache/
| paging behavior. If you sort a long, randomly ordered list by
| changing cdr's, merely traversing the resulting list cells makes for a
| terrible memory access pattern.

I think there are two many `if's in reasoning about memory access
patterns. You will traverse the list to get it into the array in the
first place, and there may be repeated traversals immediately , on the
resulting list.

But I notice you have made this point in the past, when citing
your paper which exhibited a SHUFFLE algorithm which worked on cons
cells. I could not look it up, perhaps you could post a brief
description of how it worked here?

[As for SORT Robert Maas posted a small hack that would preserve the head
cons after calling the implementation's SORT in SORT-KEEPING-HEAD-CELL
in his post[1] <News:rem-2007oct11-003@xxxxxxxxx>
Dated "11 Oct 2007 02:44:41 -0700"]

--
Madhu

[1] (rem-2007oct11-003 @ yahoo.com)
.

Relevant Pages

  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... I would tailor which algorithm to start with by how the student thinks ... If you only learn the beautiful side of programming, ...
    (comp.programming)
  • Re: puzzle
    ... >> Christopher Barber wrote: ... >> or understanding among programming professionals. ... > algorithm "close to" O. ... bubble sort, it is almost always acceptable to use an interchange sort: ...
    (comp.programming)
  • Re: The ultimate luxury ?
    ... >>My definition in terms of imposing a linear order on a set is abstract ... >>and corresponds not to the algorithm of sorting, ... > that the CS dudes of today would not know what sort means. ... Jesse Hughes ...
    (sci.physics)
  • Re: Help me with references
    ... I can't think of any situation in which bubble sort is ... > best choice for a sorting algorithm in a real machine. ... Quicksort is optimized for large Ns. ... I picked Bubblesort because your original post implied something along ...
    (comp.lang.java.help)
  • Re: Educated guesses for efficiency?
    ... it is comparatively rare for a program to run too slowly because an algorithm with the wrong big-O analysis was chosen. ... of things tended to be stored in lists). ... built-in sort function. ... Programmers *will* use algorithms with high complexities. ...
    (comp.lang.c)