LISP Sort

Thank you for your reply,

Can you please provide an example for the following list... or guide me where to look?

(97 86 45 23 87 43 26 72 35 64 63 54 89 43 89 56)

(verify your program on the following inputs)

Hi Aanvik, EE rules do not allow us to answer these questions with complete code, if it appears to be homework related. So please show me your starting point from which I will work from to get you a solution.

Sounds good.. I will do some homework and then we can fix this issue.

Thank you

This is what I have.. It sort numbers but don;t work with words.

(defun SortItems (list Order) 
  (let ((result (copy-seq list)))
    (loop for i from (1- (length result)) downto 0 do
        (loop for j from 0 to i
            when (funcall Order (aref result i) (aref result j))
               do (rotatef (aref result i) (aref result j)) ))
    result))	
 
(SortItems #(97 86 45 23 87 43 26 72 35 64 63 54 89 43 89 56) #'<)
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:

Which dialect of Lisp are you using? Can you use the string< function?

never used string<

In Common Lisp you can use:

1) string< or string-lessp for string comparisons
2) You can use write-to-string to convert a number to a string

So if you want your algorithm to sort lexically, rather then numerically, you may want to add code to convert to strings

OK. As I told I need to search google to see how I can do this. I am  very new to this.

Try this:

http://cl-cookbook.sourceforge.net/index.html

tried.. But no luck. Is there any way you can provide me some more details

Thank you.

This is how I am planning to archive this.

function MySort (L)
begin
	if L contains at most one element then return L
else
	randomly select an element e from L
	let L1 be a subset of L in which all elements are smaller than e
	L2 be a subset of L in which all elements are equal to e
	L3 be a subset of L in which all elements are greater than e
return append ( MySort (L1), L2, MySort (L3) )
endif
end function MySort

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Language aside, which sorting algorithm have you chosen to implement? This looks like Quicksort.

That's correct. Quicksort, Lacking Syntax though.

OK. Well break it down into the sub-sections you need to implemented

1) Code to choose an element from a list. For simplicity you can just choose the 1st element, that is your pivot point
2) Use the pivot value to create list of elements < pivot
3) Use the pivot value to create list of elements > pivot
4) Append / recursively call quicksort with left list, pivot and right list

Get a start, and I will help you. Like I said, I cannot start the code for you.

Take a look at remove-if and remove-if-not functions, those will help you construct the left and right lists. Also look at lambda, it can be used for the predicate for remove-if/remove-if-not

If it is too much to figure out, write a simple function to return all elements in a list that are less than a given value. Create building blocks that you can understand and easily test, then put them together into the larger function.

(remove-if #'(lambda (a)(< a 3)) '(0 1 2 3 4 5 6)))

                                              

1:

Thank you. Let me try that.

Not trying to be hard on you. I have written a quicksort for this solution, so I am referring to it as we go. Unfortunately I cannot post it in completion, since the goal is to help you learn. So feel free to ask as many questions as you need, and I will help you if you get stuck. Like I said, lets work it in phases if that helps.
 

sure, I will. And thank you for your support so far

So far I am here.. . Am I going in correct direction?

(defun MySort(myList)
	(t (append (MySort(cdr(remove-if #'(lambda (a)(< a (CAR myList))) myList)))) 

                                              

1:
2:

Also got this but looks like I am missing how to use if for string. write-to-string.

(defun Mysort (lis) 
	(if (null lis) nil
  	(let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (< a x))))
    	(append (Mysort (remove-if-not fn r)) (list x)
      		(Mysort (remove-if fn r))))))

                                              

1:
2:
3:
4:
5:

Well, in you lambda function, you are using < which is for numerics. You can use string< or string> for string comparisons.
So in your code above, try just replacing < with string<

(fn (lambda (a) (string< a x)))

                                              

1:

Thx, this works for string.. but Not working for Numbers.

I changed the code a bit but looks like I am missing something,

(defun Mysort (lis) 
        (if (null lis) nil
        (let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (string< (write-to-string a) (write-to-string x)))))
        (append (Mysort (remove-if-not fn r)) (list x)
                (Mysort (remove-if fn r))))))

                                              

1:
2:
3:
4:
5:

So the requirement is it should sort mixed lists of strings and numbers?

Not mixed but 1 function to sort both type of list... though the list will be either numbers only or string only. no mix.

Cool. That solved the problem.

Thank you.

Thank you for all your help.

Really appreciate it.

Great. Can you post the final solution, just for PAQ purposes? This was fun, its been years. Bring on the next question. ;)

Here was my version, but it works only on numbers. I did not add the conditional format conversion.

(defun quicksort (L)
   (if (null L) nil
       (let ((pivot (car L)) (rest (cdr L)))
       (append
          (quicksort
               (remove-if #'(lambda (a)(string> a pivot)) rest)
          )
          (list pivot)
          (quicksort
               (remove-if #'(lambda (a)(string< a pivot)) rest)
          )
       )
       )
   )
)
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

Sorry I meant mine only works for strings, so I would just patch in the (format ...) function to work for both.

here's the final solution.

I was wondering if I can add another param which could be > or < and based on that it will sort the list asc or desc?

(defun Mysort (lis) 
        (if (null lis) nil
	(let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (string< (format nil "~a" a) (format nil "~a" x)))))
        (append (Mysort (remove-if-not fn r)) (list x)
                (Mysort (remove-if fn r))))))

                                              

1:
2:
3:
4:
5: