AutoLISP
1 messages in this thread
#132108-AutoLISP —
declared parent_msg_num=132108,
resolved parent_id points to #(unresolved)
I relized there's a way to do the innermost loop more
efficiently, so here's a better version of (bsort):
; A routine to sort a list of items using the bubble sort algorithm.
; The bubble sort isn't particularly fast, but it's simple and needs
; no auxiliary storage. An auxiliary list equal in size to the
; original list is used in this implementation, because AutoLISP
; doesn't provide any way to reach into a list and swap two elements.
; Arguments:
; inlist = the list to be sorted
; rank_f = the name of a function which takes two arguments (each one
; an element of the list to be sorted). The function must
; return non-NIL if the first argument is "greater than" the
; second (that is, the first argument should follow the second
; in a sorted list) and NIL if the two arguments are "equal"
; or the first argument is "less than" the second.
; Return value:
; The sorted list
(defun bsort (inlist rank_f / l_len n_pair swap el_num tmplst count)
; Initialize flag that we've changed the position of at least
; one element of the list
(setq swap T
; The length of the list
l_len (length inlist)
; Store the number of list element pairs that we have to check
n_pair (1- l_len)
)
; As long as we've changed the position of at least one element …
(while swap
; Set flag that we haven't made any changes in this iteration
(setq swap NIL
; Set pointer to the current element in the list
el_num -1
)
; Loop through all the elements of the list that we have to check.
(while (> n_pair (setq el_num (1+ el_num)))
; If the current element is "greater than" the next element …
(if (rank_f (nth el_num inlist) (nth (1+ el_num) inlist))
(progn
; Swap the current element and the next. Initialize …
(setq count -1
tmplst NIL
)
; Copy list elements into the auxiliary list, up to the pair
; to be swapped
(while (> el_num (setq count (1+ count)))
(setq tmplst (cons (nth count inlist) tmplst))
)
; Copy the pair to be swapped, swapping them
(setq tmplst (cons (nth (1+ count) inlist) tmplst)
tmplst (cons (nth count inlist) tmplst)
count (1+ count)
)
; Copy the list elements after the pair to be swapped
(while (> l_len (setq count (1+ count)))
(setq tmplst (cons (nth count inlist) tmplst))
)
; Move the auxiliary list back into the master list (note that
; we built the auxiliary list in reverse order)
(setq inlist (reverse tmplst)
; Set flag that we've made at least one swap
swap T
)
)
)
)
; We've passed all the way through the list. At the end of the first
; pass, the "greatest" element is known to be at the end of the list.
; At the end of the second pass, the "second greatest" eelement
; is known to be second to the end of the list. In other words, after
; each pass we can reduce the nubmer of element pairs to check by one
(setq n_pair (1- n_pair))
)
; The list is all sorted, evaluate it to get the return value
inlist
)
jrf