Perl-Python-a-Day: Sorting

[Ulrich Hobelmann]

Xah Lee wrote:
> To sort a list in Python, use the “sort” method. For example:
> 
> li=[1,9,2,3];
> li.sort();
> print li;

Likewise in Common Lisp.  In Scheme there are probably packages for that 
as well.  My apologies for not being very fluent anymore.

CL-USER> (setf list (sort '(1 9 2 3) #'<))	; input
(1 2 3 9)					; output

The second argument is mandatory too (comparison function).

> Note that sort is a method, and the list is changed in place.

Same here.  To be safe, assign the result to "list".

> Suppose you have a matrix, and you want to sort by second column.
> Example Solution:
> 
> li=[[2,6],[1,3],[5,4]]
> li.sort(lambda x, y: cmp(x[1],y[1]))
> print li; # prints [[1, 3], [5, 4], [2, 6]]

CL-USER> (setf list (sort '((2 6) (1 3) (5 4))
			  #'(lambda (x y) (< (second x) (second y)))))
((1 3) (5 4) (2 6))	; output

> The argument to sort is a function of two arguments, that returns -1,
> 0, 1. This function is a decision function that tells sort() how to
> decide the order of any two elements in your list. If the first
> argument is “less” then second argument, the function should return
> -1. If equal, then 0. Else, 1.

In CL you only need a smaller-than function.  I guess if elements are 
"equal", they don't need sorting anyway.

> li=[
> 'my283.jpg',
> 'my23i.jpg',
> 'web7-s.jpg',
> 'fris88large.jpg',
> ]

CL-USER> (setf list '("my283.jpg" "my23i.jpg" "web7-s.jpg" 
"fris88large.jpg"))

> def myComp (x,y):
>     import re
>     def getNum(str): return float(re.findall(r'\d+',str)[0])
>     return cmp(getNum(x),getNum(y))

CL-USER> (defun my-comp (x y)
	   (flet ((getnum (s)
		    (parse-integer s :start (position-if #'digit-char-p s)
				   :junk-allowed t)))
	     (< (getnum x) (getnum y))))

> li.sort(myComp)
> print li # returns ['web7-s.jpg', 'my23i.jpg', 'fris88large.jpg',
> 'my283.jpg']

CL-USER> (setf list (sort list #'my-comp))
("web7-s.jpg" "my23i.jpg" "fris88large.jpg" "my283.jpg") ; output

> li=[[2,6],[1,3],[5,4]]
> li.sort(key=lambda x:x[1] ) # is equivalent to the following
> #li.sort(lambda x, y: cmp(x[1],y[1]))
> print li; # prints [[1, 3], [5, 4], [2, 6]]

CL-USER> (setf list (sort '((2 6) (1 3) (5 4)) #'< :key #'second))
((1 3) (5 4) (2 6)) ; output

Here some people might jump in and say "lists might be more readable 
than vectors, but lists are slow."
If they are slow for your data set, just use vectors instead ;)

-- 
State, the new religion from the friendly guys who brought you fascism.