Mergesort-divide list to lists of two argument

Discussion of Common Lisp

Mergesort-divide list to lists of two argument

Postby fetastein » Sat Sep 10, 2011 7:10 am

*In advance, I apologize my poor English!*

Hello!
I'm making "merge sort" program. I've been making a program that merges two lists.
And,I'll use embeded sort program as sort process in mergesort.

I have problem in first step of mergesort algorithm.
Correct program will divide list like this.
Code: Select all
(dividetwo '(1 2 3 4 5))
((1 2) (3 4) (5))

But my program work like this.
Code: Select all
CL-USER> (dividetwo '(1 2 3 4 5))
((1 2) ((3 4) ((5))))


Below is my dividetwo program.
Code: Select all
(defun divideTwo (list)
  "this function (will) divide list into lists of list that contains two argument"
  (defun divideTwo-iter (list)
    (cond ((null (cdr list)) list)
     ((null (cddr list)) list)
     (t (values  (list (car list) (cadr list)) (divideTwo (cddr list))))))
  (multiple-value-list (divideTwo-iter list))


I don't know why this program doesn't work.
Please tell me the way to modify this program or more better way to divide list into list of lists.
fetastein
 
Posts: 2
Joined: Sat Sep 10, 2011 3:00 am

Re: Mergesort-divide list to lists of two argument

Postby adam33147 » Sun Sep 11, 2011 8:27 am

You dont need the embedded defun dividetwo-iter. I looks like you are trying to have a local funtion via the embedded defun. This would be accomplished with the labels form.

Code: Select all
(defun name (x)
   (labels ((fun-name (var-a var-b)
                  (+ a b)))
      (fun-name x 10))


The way you have it would end up redefining the global function dividetwo-iter on every call to divide two. This clutters up the global namespace, and could cause a bug that is very difficult to find. Using labels as a local function makes intent more clear.

The end condition from the recurtion should return the list embedded in a list, and there is no need for the multiple-value-list, or values form. The values call is like adding another dimension to the return value, and also can allow for backwards compatability if you decide to add data to the return value later.

Instead of the values use the cons.

Here is what I wrote, I hid it (you have to scroll down) in case you want to figure it out yourself.
Code: Select all
.
.
.
.
.
.
.
.
.
.
.
.
.
(defun divideTwo (list)
      "this function (will) divide list into lists of list that contains two argument"
      (cond ((or (null (cdr list))
            (null (cddr list)))
        (list list))
       (t
        (cons (list (car list) (cadr list)) (divideTwo (cddr list))))))
adam33147
 
Posts: 20
Joined: Sat Aug 20, 2011 6:49 pm

Re: Mergesort-divide list to lists of two argument

Postby edgar-rft » Sun Sep 11, 2011 11:55 am

This is Common Lisp, not Scheme. There's no need for recursion. Common Lisp has builtin iteration support:

Code: Select all
(defun divide-two (input-list)
  "Divide INPUT-LIST into sublists of two arguments."
  (loop until (null input-list)
        collect (if (rest input-list)
                    (list (pop input-list) (pop input-list))
                    (list (pop input-list)))))


HTH - edgar
edgar-rft
 
Posts: 147
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Mergesort-divide list to lists of two argument

Postby fetastein » Wed Sep 28, 2011 4:35 am

Thank you for your help! Sorry to reply lately.
fetastein
 
Posts: 2
Joined: Sat Sep 10, 2011 3:00 am


Return to Common Lisp

Who is online

Users browsing this forum: Google [Bot] and 1 guest

cron