Adding element to a sorted list

[ykm]

Hi,
I am trying to develop a function which does as mentioned in the subject line i.e adding an element to a list while maintaining the sort order. The following is what I have managed:

Code: Select all

(defun sort-push(lst n &key (test #'<) (key #'identity))
   (labels ((rec (lst n acc)
         (if (null lst)
        (reverse (cons n acc))
        (if (funcall test (funcall key n) (funcall key (car lst)))
            (append (reverse (cons n acc)) lst)
            (rec (cdr lst) n (cons (car lst) acc))))))
     (rec lst n ())))

(sort-push '((1 . 2) (5 . 6))  (3 . 4) :key #'cdr)
((1 . 2) (3 . 4) (5 . 6))


This function is resulting into what is being expected. However, it appears something isn't right about it. Can you point out the drawbacks of this function? Its taking a long time to push an element into a huge list of cons. Also, please point out if this functionality has been already implemented into the current list implementations.

Regards,
ykm.

[Konfusius]

Code: Select all

(defun sorted-push (lst n &key (test #'<) (key #'identity))
  (if (null lst)
   (cons n nil)
   (if (funcall test (funcall key n) (funcall key (car lst)))
     (cons n lst)
     (cons (car lst) (sorted-push (cdr lst) n :test test :key key)))))

(sorted-push '((1 . 2) (5 . 6)) '(3 . 4) :key #'cdr)

[Goheeca]

Your function is O(N) if I'm not mistaken. I've created this:

Code: Select all

(defun sort-push (lst n &key (test #'<) (key #'identity))
  (let ((mid (floor (/ (length lst) 2))))
    (flet ((split (lst where) (values (subseq lst 0 where) (subseq lst where)))
           (comp (a b) (funcall test (funcall key a) (funcall key b))))
      (cond ((null lst) (list n))
            ((comp n (nth mid lst)) (multiple-value-bind (left right) (split lst mid)
                                      (append (sort-push left n :test test :key key) right)))
            ((= 1 (length lst)) (list (nth mid lst) n))
            (t (multiple-value-bind (left right) (split lst mid)
                 (append left (sort-push right n :test test :key key))))))))

it's a draft, thus it can be improved probably (especially the (= 1 (length lst)) part). It has O(log N).

[Goheeca]

But it's not good for lists because of the inefficiency of subseq on lists, for vectors (the function must be adapted) it would be reasonable.

[edgar-rft]

Why not just simply writing:

Code: Select all

(defun sort-push (lst n &key (test #'<) key)
  (sort (cons n lst) test :key key))

The built-in SORT is probably faster than traversing the list.

- edgar

[sylwester]

Konfusius's is the fastes judging by my test which adds 1000 random numbers to an empty list.
WIth a litte change to the tail recusive version it matches it:

Code: Select all

(defun sort-push-iter(lst n &key (test #'<) (key #'identity))
   (labels ((rec (lst n acc)
         (if (null lst)
        (nreverse (cons n acc))
        (if (funcall test (funcall key n) (funcall key (car lst)))
            (nconc (nreverse (cons n acc)) lst)
            (rec (cdr lst) n (cons (car lst) acc))))))
     (rec lst n ())))


Using built in sort was the worst with my tests, but I liked the idea.
In the spirit of Goheeca's idea and my test with random numbers I guess you get the best result if instead of maintaining a list actually maintained a binary tree and when finished inserting converted it to a sorted list

[ykm]

Hi,
Thanks to all of you for your responses. One thing I forgot to mention in the original question is that I am using this function in a loop and using the built-in sort after adding each element(as I needed the sorted list for the next iteration as well) sounded inefficient to me.

Gohecca: Yes, indeed, its complexity if O(n), with the worst case requiring computations until the length of the list. Though, it appears in your code, you have incorporated quick sort into it. Will look into that.

Edgar: I had used it, but it wasn't upto the mark hence the function.

Regards,
ykm.

[Goheeca]

It's not a quicksort but the binary search thorough it's not good on linked lists.

[sylwester]

Hi,
Thanks to all of you for your responses. One thing I forgot to mention in the original question is that I am using this function in a loop and using the built-in sort after adding each element(as I needed the sorted list for the next iteration as well) sounded inefficient to me.

So you add to a list, then sort it because you need to use the list in each iteration. How do you use the sorted list/ WHat do you access?

[Paul]

it's a draft, thus it can be improved probably (especially the (= 1 (length lst)) part). It has O(log N).

FWIW, for (= 1 (length list)) do (null (cdr list)) -- or reverse that and the T clause and drop the NULL.

Does this thing have to be nondestructive? I want to write something like

Code: Select all

(defun insert-in-ordered-list (n list &key (test #'<) (key #'identity))
  (loop with val = (funcall key n) for p = nil then x as x on list
     while (funcall test (funcall key (car x)) val)
     finally (return (if p
          (progn (setf (cdr p) (cons n (cdr p))) list)
          (cons n list)))))


(Note: I put the arguments in the right order)