[plt-scheme] (Slightly Off) Looking for a Sorting Algorithm

On Nov 18, 2005, at 3:37 AM, Erich Rast wrote:

> Hi fellow Schemers,
>
> For some project that has to do with linear natural language syntax  
> I need a sorting algorithm that doesn't just pass two elements of a  
> list for comparison, but the intermediary lists that could be  
> constructed if the comparison would turn out true or false  
> respectively, plus the positions of the elements to compare. To  
> illustrate this, I'll best give an example:
>
> input: (2 6 3 7 1)
>
> instead of comparing, say, (less-than? 3 6), the comparison  
> function would get
>
> (less-than? '(2 3 6 7 1) 1 '(2 6 3 7 1) 2)
>
> instead of comparing, say, (less-than? 7 6), the comparison  
> function might get, for example,
>
> (less-than? '(2 7 6 3 1) 1 '(2 6 7 3 1) 2)
>
> I don't care whether the sorting algorithm swaps values or gives  
> other intermediary results as in the second example, as long as it  
> can provide those intermediary results. The reason I need this is  
> that my comparison function depends on the relative position of the  
> elements compared to each other and possibly to other elements in  
> the list. Furthermore, the algorithm ought to be stable, i.e. may  
> not swap elements that are equal, and of course and as always, the  
> more efficient, the better. To avoid list-ref, a vector-based  
> algoritm would also be great.
>
> Is there such a thing? Any ideas? Do sorting algorithms of this  
> kind have a special name?
>
> I'd very much appreciate any help, since this is for a real-world  
> project and I'm under time pressure.

In the problem you describe, what does it mean for the list to be  
sorted?

Typically, a list is "sorted" when the comparison relation for  
elements holds for each adjacent pair in the list.  In your problem,  
it appears to mean something different.

In fact, my reading of your problem suggests that for many comparison  
functions, there is no non-exponential search algorithm.  In other  
words, you have to just "try all the sequences."  Can you narrow down  
the problem a bit?

John Clements

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2430 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20051118/e48b703c/attachment.p7s>