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

From: Erich Rast (erich at snafu.de)
Date: Fri Nov 18 06:37:32 EST 2005

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.

Best regards,

Erich



Posted on the users mailing list.