Mergesort-divide list to lists of two argument

Discussion of Common Lisp
Post Reply
fetastein
Posts: 2
Joined: Sat Sep 10, 2011 3:00 am

Mergesort-divide list to lists of two argument

Post by 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.

adam33147
Posts: 20
Joined: Sat Aug 20, 2011 6:49 pm

Re: Mergesort-divide list to lists of two argument

Post by 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))))))

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

Re: Mergesort-divide list to lists of two argument

Post by 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

fetastein
Posts: 2
Joined: Sat Sep 10, 2011 3:00 am

Re: Mergesort-divide list to lists of two argument

Post by fetastein » Wed Sep 28, 2011 4:35 am

Thank you for your help! Sorry to reply lately.

Post Reply