Quicksort?

Discussion of Common Lisp
Post Reply
Cass
Posts: 6
Joined: Thu Oct 24, 2013 8:14 am

Quicksort?

Post by Cass » Thu Oct 24, 2013 9:21 am

Hello,

Could anyone help me with kinda my kinda clueless fumbling? ^_^; (I'm kinda new to the whole programming thing.)

I was thinking that it'd be kinda neat to be able to take the data from my school work and run correlation tests on everything against everything. I'm trying to implement quicksort as the first step in doing that.

Anyway, first I tried writing it out like this:

Code: Select all

(defun test (lst)
  (let ((pivot (car lst))
	(smaller-than (remove-if (< pivot) lst) )
	(larger-than (remove-if (> pivot) lst) ))
    (setf pivot (cons (test smaller-than) pivot))
    (cons pivot (test larger-than))))
However SBCL is complained that pivot isn't defined yet:

Code: Select all

 warning: 
    undefined variable: PIVOT
    --> PROGN 
    ==>
      (THE REAL PIVOT)
Which was kinda confusing me because I told it what pivot was as the first thing.

I did think maybe you weren't allowed have one definition in let dependent on something else in the let. Which seems supported by a quick test in the REPL:

Code: Select all

(let (
	       (x 1)
	       (y (+ x 1))))
; in: LET ((X 1) (Y (+ X 1)))
;     (LET ((X 1) (Y (+ X 1)))
;       )
; 
; caught STYLE-WARNING:
;   The variable X is defined but never used.
; 
; caught STYLE-WARNING:
;   The variable Y is defined but never used.

; in: LET ((X 1) (Y (+ X 1)))
;     (+ X 1)
; 
; caught WARNING:
;   undefined variable: X
Anyway, then I tried this:

Code: Select all

(defun test (lst)
  (defvar pivot (car lst))
  (defvar smaller-than (remove-if (< pivot) lst) )
  (defvar larger-than (remove-if (> pivot) lst) )

    (setf pivot (cons (test smaller-than) pivot))
    (cons pivot (test larger-than))))
Which among other things said -

Code: Select all

  warning: 
    undefined variable: PIVOT
    --> PROGN 
    ==>
      (THE REAL PIVOT)
    
  warning: undefined variable: SMALLER-THAN
I suppose it makes sense that smaller-than wouldn't be defined if pivot wasn't. But then why's larger-than not throwing its own warning?

Did think I might not understand how defvar was used but this works:

Code: Select all

(defvar x (car '(1 2)))

=> X

X

=> 1
So, yeah, I'm just kinda really confused now.

SBCL if that's relevant.

Thanks! Apologies if this is in the wrong place ^_^

saulgoode
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: Quicksort?

Post by saulgoode » Thu Oct 24, 2013 5:58 pm

The bindings in a let block are not guaranteed to be handled in sequence. They might be evaluated in a different order than specified, or evaluated in parallel on a multi-threaded implementation.

If you wish to have the bindings evaluated in a specific order (so later bindings can reference earlier ones) then you should use let*.

Code: Select all

  (let* ((x 10)
   (y 20)
   (z (+ x y)) )
    (print z) )

Cass
Posts: 6
Joined: Thu Oct 24, 2013 8:14 am

Re: Quicksort?

Post by Cass » Sat Oct 26, 2013 4:35 pm

Ah, excellent. Thank you! :D

Post Reply