CODEWITHSUNDEEP
lispschemeracket
cougar
cougar

Reputation: 185

LISP Combining two list of integers and sorting them in ascending order?

I have no problem combining the lists but sorting them in ascending order is where i am struggling. 

 (define (combineASC l1 l2)
   (cond 
     ((null? l1) l2)
     (#t (cons (car l1) (combineASC (cdr l1) l2)))
     (sort l2 #'<))) ; I found this part in an online source

This is the output i get:

(combineASC '(2 4 6) '(1 4 5))

(2 4 6 1 4 5)

Does anyone have any suggestions for me?

Upvotes: 0

Views: 4946

Answers (3)

user797257
user797257

Reputation:

Because tail recursive :)

(define (merge-sorted . lists)
  (define (%merge-sorted head tails)
    (cond
     ((null? tails) head)
     ((null? (car tails))
      (%merge-sorted head (cdr tails)))
     (else (let ((sorted
                  (sort tails
                        (lambda (a b)
                          (<= (car a) (car b))))))
             (%merge-sorted (cons (caar sorted) head)
                            (cons (cdar sorted) (cdr sorted)))))))
  (reverse (%merge-sorted '() lists)))

(merge-sorted '(1 2 3) '(4 5 6 7 8 9) '(2 4 6) '(1 3 5 7))
  • it scales better :P

I think this is what Will was talking about:

(define (merge-sorted . lists)
  (define (%swap-if-greater lists)
    (define (%do-swap head next built tails)
      (cond
       ((null? tails)
        (append (reverse built)
                (cond
                 ((null? next) (list head))
                 ((> (car head) (car next))
                    (list next head))
                 (else (list head next)))))
       ((> (car head) (car next))
        (%do-swap head (car tails)
                  (cons next built) (cdr tails)))
       (else (append (reverse built)
                     (list head) (list next) tails))))
    (%do-swap (car lists)
              (if (null? (cdr lists)) '() (cadr lists))
              '() (if (null? (cdr lists)) '() (cddr lists))))
  (define (%merge-sorted head tails)
    (cond
     ((null? tails) head)
     ((null? (car tails))
      (%merge-sorted head (cdr tails)))
     (else (let ((sorted (%swap-if-greater tails)))
             (%merge-sorted (cons (caar sorted) head)
                            (cons (cdar sorted)
                                  (cdr sorted)))))))
  (reverse
   (%merge-sorted
    '() (sort lists (lambda (a b) (<= (car a) (car b)))))))

Especially given Schemes... interesting position on booleans, I wouldn't be very enthusiastic about this one.

Upvotes: 1

Will Ness
Will Ness

Reputation: 71109

So you're combining two input lists, each already sorted in ascending order. You want to "weave" them into one, also in ascending order.

For that, you just take both head elements (each from each input list) and compare; then you take the smallest out from its list, and combine further what you're left with - using same function.

There will be no sorting involved. The resulting list will be already sorted, by virtues of the process that defines it.

This operation is commonly called "merge". It preserves duplicates. Its duplicates-removing counterpart, merging two ordered lists into one as well, is known a "union". That is because these ordered (non-descending, or strictly ascending) lists can be seen as representation of sets.

Another subtlety to take note of is, what to do when the two head elements are equal. We've already decided to preserve the duplicates, yes, but which of the two to take out first?

Normally, it's the left one. Then when such defined merge operation is used as part of merge sort, the sort will be stable (of course the partitioning has to be defined properly for that too). Stable means, the original order of elements is preserved.

For example, if the sort is stable, when sorting by the first element of pairs, (3,1) (1,2) (3,3) is guaranteed to be sorted as (1,2) (3,1) (3,3) and not as (1,2) (3,3) (3,1).

So, following the skeleton of your code, we get

;; combine two non-decreasing lists into one non-decreasing list,
;; preserving the duplicates
(define (combineNONDECR l1 l2)
   (cond 
     ((null? l1) l2)
     ((null? l2) l1)
     ((<= (car l1) (car l2))
      (cons (car l1) (combineNONDECR (cdr l1) l2)))
     (t
      (cons (car l2) (combineNONDECR l1 (cdr l2))))))

But if you really need the result to be in ascending order, as opposed to non-decreasing, then you'd have to tweak this a little bit - make the = case separate, and handle it separately, to stop the duplicates from creeping in (there are no duplicates in each of the ascending-order lists, but the lists might contain some duplicates between the two of them).

Upvotes: 4

elyashiv
elyashiv

Reputation: 3691

(defun merge (l1 l2)
 (if (not (and (eql nil l1) (eql l2 nil))
  (if (> (car l1) (car l2))
     (cons (car l1) (merge (cdr l1) l2))
    (cons (car l2) (merge (cdr l2) l1)))
  ;;;append the not-nil string to the rest.
  )

that should work (you still need to complete the code, but the idea is clear)

note this code is in common-lisp.

look up merge sort for more info about the technique

Upvotes: 0

Related Questions