Sorting small fixed number of elements
Nordlöw
(sorting) algorithms in general. I am namely looking for optimized
sorting algorithms for 3,4,5,... number of elements.
I already have code for two and three number of elements:
/*!
* Sort @p a and @p b inline.
*/
#undef SORT2
#define SORT2(a, b) { \
if ((a) > (b)) SWAP((a), (b)); \
}
/*!
* Sort @p a, @p b and @p c inline.
*/
#undef SORT3
#define SORT3(a, b, c) { \
SORT2(a, b); \
SORT2(b, c); \
SORT2(a, b); \
}
Thanks in advance,
Nordlöw
Nordlöw
I figured out how to think about these algorithms...
/Nordlöw
Pascal J. Bourguignon
> On Nov 30, 1:05�pm, Nordl�w <per.nord...@gmail.com> wrote:
>> Does anyone know of any nice forum/group that answers question about
>> (sorting) algorithms in general. I am namely looking for optimized
>> sorting algorithms for 3,4,5,... number of elements.
>>
>> I already have code for two and three number of elements:
>>
>> /*!
>> �* Sort @p a and @p b inline.
>> �*/
>> #undef �SORT2
>> #define SORT2(a, b) { � � � � � � � � � � � � � \
>> � � if ((a) > (b)) SWAP((a), (b)); � � � � � � �\
>> � }
>>
>> /*!
>> �* Sort @p a, @p b and @p c inline.
>> �*/
>> #undef �SORT3
>> #define SORT3(a, b, c) { � � � � � � � � � � � �\
>> � � SORT2(a, b); � � � � � � � � � � � � � � � �\
>> � � SORT2(b, c); � � � � � � � � � � � � � � � �\
>> � � SORT2(a, b); � � � � � � � � � � � � � � � �\
>> � }
>>
>> Thanks in advance,
>> Nordl�w
>
> I figured out how to think about these algorithms...
Thanks. What about the others who didn't figure it out? Will we tell
them?
--
__Pascal Bourguignon__
Pascal J. Bourguignon
> Does anyone know of any nice forum/group that answers question about
> (sorting) algorithms in general.
news:comp.programming
> I am namely looking for optimized
> sorting algorithms for 3,4,5,... number of elements.
>
> I already have code for two and three number of elements:
>
> /*!
> * Sort @p a and @p b inline.
> */
> #undef SORT2
> #define SORT2(a, b) { \
> if ((a) > (b)) SWAP((a), (b)); \
> }
>
> /*!
> * Sort @p a, @p b and @p c inline.
> */
> #undef SORT3
> #define SORT3(a, b, c) { \
> SORT2(a, b); \
> SORT2(b, c); \
> SORT2(a, b); \
> }
>
> Thanks in advance,
> Nordl�w
Here is how I would do it.
I would have a lisp function generate-fixed-sort-tree/c to which I
would give a list of input variables, a list of output variables, and
the name of a comparison function (you can always write
#define less(a,b) ((a)<(b))
):
(generate-fixed-sort-tree/c '(\a \b \c \d) '(\w \x \y \z) '|less|)
and it would produce an expression like the following (indenting by emacs):
if(less(c,d))
if(less(b,d))
if(less(b,c))
if(less(a,c))
if(less(a,b))
{ w=a; x=b; y=c; z=d; }
else
{ w=b; x=a; y=c; z=d; }
else
if(less(a,d))
{ w=b; x=c; y=a; z=d; }
else
{ w=b; x=c; y=d; z=a; }
else
if(less(a,b))
if(less(a,c))
{ w=a; x=c; y=b; z=d; }
else
{ w=c; x=a; y=b; z=d; }
else
if(less(a,d))
{ w=c; x=b; y=a; z=d; }
else
{ w=c; x=b; y=d; z=a; }
else
if(less(a,d))
if(less(a,c))
{ w=a; x=c; y=d; z=b; }
else
{ w=c; x=a; y=d; z=b; }
else
if(less(a,b))
{ w=c; x=d; y=a; z=b; }
else
{ w=c; x=d; y=b; z=a; }
else
if(less(b,c))
if(less(b,d))
if(less(a,d))
if(less(a,b))
{ w=a; x=b; y=d; z=c; }
else
{ w=b; x=a; y=d; z=c; }
else
if(less(a,c))
{ w=b; x=d; y=a; z=c; }
else
{ w=b; x=d; y=c; z=a; }
else
if(less(a,b))
if(less(a,d))
{ w=a; x=d; y=b; z=c; }
else
{ w=d; x=a; y=b; z=c; }
else
if(less(a,c))
{ w=d; x=b; y=a; z=c; }
else
{ w=d; x=b; y=c; z=a; }
else
if(less(a,c))
if(less(a,d))
{ w=a; x=d; y=c; z=b; }
else
{ w=d; x=a; y=c; z=b; }
else
if(less(a,b))
{ w=d; x=c; y=a; z=b; }
else
{ w=d; x=c; y=b; z=a; }
For each input, there are n or n+1 comparisons, and n assignments.
(We cannot really say that the algorith is O(n) in time since we
never go asymptotically with it). In effect we are expanding all the
permutations in the branches (n! branches) of this if tree, so we
really don't want to expand it for more than a few variables.
Since there is no overwriting of the variable, I'd expect it to go
faster on modern hardware.
If you wanted to sort in place, it could be modified produce in the
branches the minimal exchanges needed to implement each permutation,
or you could just put back the output-variables into the
input-variables, again, given the small number of values, there's no
point in swapping thru a single temporary.
;; Common Lisp code follows. Notice that we use a closure, so care is
;; in order to run it in emacs lisp.
;; This generate-fixed-sort-tree/c generates the C code from a if-tree
;; built by generate-fixed-sort-tree.
(defun generate-fixed-sort-tree/c (input-variables output-variables lessp)
(assert (= (length input-variables) (length output-variables)))
(assert (< 1 (length input-variables)))
(labels ((walk-if-tree (node)
;; (print `(walk-if-tree ,node))
(if (and (listp node) (eql 'order (first node)))
(format nil "{ ~:{~A=~A; ~}}~%"
(mapcar (function list) output-variables (rest node)))
(format nil "if(~A(~A,~A))~%~Aelse~A"
lessp (second (second node)) (third (second node))
(walk-if-tree (third node))
(walk-if-tree (fourth node))))))
(walk-if-tree (generate-fixed-sort-tree input-variables))))
;; The function generate-fixed-sort-tree would take the list of input
;; variables, and produce the if-tree, by processing each variable in
;; turn. The variable will be compared to the variables ordered by
;; the subtrees, to find out where to insert it by intercal-variable.
(defun generate-fixed-sort-tree (input-variables)
(assert (< 1 (length input-variables)))
(if (= 2 (length input-variables))
`(if (< ,@input-variables)
(order ,@input-variables)
(order ,@(reverse input-variables)))
(intercal-variable (first input-variables)
(generate-fixed-sort-tree (rest input-variables)))))
;; (generate-fixed-sort-tree '(a b c))
;;
;; (IF (< B C)
;; (IF (< A C)
;; (IF (< A B)
;; (ORDER A B C)
;; (ORDER B A C))
;; (ORDER B C A))
;; (IF (< A B)
;; (IF (< A C)
;; (ORDER A C B)
;; (ORDER C A B))
;; (ORDER C B A)))
;; intercal-variable is the workhorse of the algorithm. It takes a
;; if-tree, finds the leaf (order ...) nodes, and replace them with a
;; new subtree where the variable is compared and inserted in order.
;; This is done by producing a sequence of lists where the variable is
;; inserted in each position, and a binary tree of the variables from
;; (order ...) taken as an infix walk. Then the leaves of this
;; order-tree, which represent each position where the variable may be
;; inserted are replaced by the (order ...) from the sequences.
(defun intercal-variable (variable if-tree)
"
IF-TREE: a tree where the nodes are (IF (< <x> <y>) <then-child> <else-child>)
and where the leafs are (ORDER <x1> <x2> ... <xN>).
RETURN: A new tree where each leaf is replaced by a IF subtree positionning
the VARIABLE in the right position in the decendent ORDERs.
"
(let ((leaf (list 'leaf)))
(labels ((walk-variable-tree (node func)
;; (print `(walk-variable-tree ,node ,func))
(if (eql leaf node)
(funcall func)
`(if (< ,variable ,(first node))
,(walk-variable-tree (second node) func)
,(walk-variable-tree (third node) func))))
(insert-variable (order)
;; (print `(insert-variable ,order))
(let ((sequences (insert-in-each-position order variable)))
(walk-variable-tree (order-to-tree order leaf)
(lambda () `(order ,@(pop sequences))))))
(walk-if-tree (node)
;; (print `(walk-if-tree ,node))
(if (and (listp node) (eql 'order (first node)))
(insert-variable (rest node))
(list (first node) (second node)
(walk-if-tree (third node))
(walk-if-tree (fourth node))))))
(walk-if-tree if-tree))))
;; (intercal-variable 'x '(order a b c d e))
;;
;; (IF (< X C)
;; (IF (< X B)
;; (IF (< X A)
;; (ORDER X A B C D E)
;; (ORDER A X B C D E))
;; (ORDER A B X C D E))
;; (IF (< X E)
;; (IF (< X D)
;; (ORDER A B C X D E)
;; (ORDER A B C D X E))
;; (ORDER A B C D E X)))
;; (intercal-variable 'x '(order a b c d e f g))
;;
;; (IF (< X D)
;; (IF (< X B)
;; (IF (< X A)
;; (ORDER X A B C D E F G)
;; (ORDER A X B C D E F G))
;; (IF (< X C)
;; (ORDER A B X C D E F G)
;; (ORDER A B C X D E F G)))
;; (IF (< X F)
;; (IF (< X E)
;; (ORDER A B C D X E F G)
;; (ORDER A B C D E X F G))
;; (IF (< X G)
;; (ORDER A B C D E F X G)
;; (ORDER A B C D E F G X))))
;; And remains the utility subfunctions used above:
(defun split-in-two (list)
(labels ((advance (slow fast prefix)
(if (null (cdr fast))
(values (car slow) (nreverse prefix) (cdr slow))
(advance (cdr slow) (cddr fast) (cons (car slow) prefix)))))
(advance list list '())))
;; (mapcar (lambda (in) (multiple-value-list (split-in-two in))) '(() (a) (a b) (a b c) (a b c d) (a b c d e) (a b c d e f) (a b c d e f g)))
;; ((NIL NIL NIL) (A NIL NIL) (B (A) NIL) (B (A) (C)) (C (A B) (D))
;; (C (A B) (D E)) (D (A B C) (E F)) (D (A B C) (E F G)))
(defun order-to-tree (order leaf)
(cond ((null order) leaf) ; leaf
(t (multiple-value-bind (pivot left right) (split-in-two order)
(list pivot
(order-to-tree left leaf)
(order-to-tree right leaf))))))
;; (mapcar (lambda (order) (order-to-tree order '\.)) '(() (a) (a b) (a b c) (a b c d) (a b c d e) (a b c d e f) (a b c d e f g)))
;; -->
;; (|.|
;;
;; (A |.| |.|)
;;
;; (B (A |.| |.|)
;; |.|)
;;
;; (B (A |.| |.|)
;; (C |.| |.|))
;;
;; (C (B (A |.| |.|)
;; |.|)
;; (D |.| |.|))
;;
;; (C (B (A |.| |.|)
;; |.|)
;; (E (D |.| |.|)
;; |.|))
;;
;; (D (B (A |.| |.|)
;; (C |.| |.|))
;; (F (E |.| |.|)
;; |.|))
;;
;; (D (B (A |.| |.|)
;; (C |.| |.|))
;; (F (E |.| |.|)
;; (G |.| |.|)))
;; )
(defun insert-in-each-position (order variable)
(if (null order)
(list (list variable))
(cons (cons variable order)
(mapcar (lambda (suborder) (cons (first order) suborder))
(insert-in-each-position (rest order) variable)))))
;; (insert-in-each-position '(a b c d e) 'x)
;; ((X A B C D E) (A X B C D E) (A B X C D E) (A B C X D E) (A B C D X E)
;; (A B C D E X))
--
__Pascal Bourguignon__