Pages: [1]   Go Down
Print
Author Topic: QuickSort in scheme  (Read 2317 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« on: 19-03-2011, 17:51:04 »

Ecco finalmente il quicksort  yoh... sono veramente felice di essere riuscito ad implementarlo perche' ho risolto uno dei problemi che ieri mi ha portato a scegliere il mergesort bottom-up piuttosto che quello top-down: come fare a far valutare piu' di un espressione da una funzione? spulciando nella documentazione di scheme ho trovato la funzione let che mi permette proprio di fare quello che mi serviva.
P.s. Questa volta spero di aver scritto qualcosa che le piaccia prof xD
Code:
(define (sorted? prec? ls)
  (or (null? ls)
      (null? (cdr ls))
      (and (prec? (car ls) (cadr ls)) (sorted? prec? (cdr ls)))))

;; partition function return a list with 2 partitions.
;; The first one contains all the elements prec? of the pivot while the second one contains all the others
(define (partition pivot ls part1 part2 prec?)
  (cond
    ((null? ls)
     (list (append part1 (list pivot)) part2))
    ((prec? (car ls) pivot)
     (partition pivot (cdr ls) (append part1 (list (car ls))) part2 prec?) )
    (else
     (partition pivot (cdr ls) part1 (append part2 (list (car ls))) prec?) )))

;; quicksortnumber function sorts the list in input using the quicksort algorithm
(define (quicksortnumber ls prec?)
  (let ([parts (partition (car ls) (cdr ls) empty empty prec?)])
    (if (sorted? prec? ls)
        ls
        (append (quicksortnumber (car parts) prec?) (quicksortnumber (cadr parts) prec?)) )))


;; Test
(define tosort (list 21 13 40 31 11 34 16 18 62 38 14 51 72 9))
(quicksortnumber tosort <)
(quicksortnumber tosort >)
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #1 on: 19-03-2011, 18:56:44 »

la funzione partition e' il piu' chiaro esempio
di come sia difficile evitare di pensare imperativo per chi
lo fa da anni.
Per funzionare funziona. Aggiungiamo anche che e' molto efficiente.
Pero' e' una funzione in cui part1 e part2 giocano il ruolo di due accumulatori
che andiamo man mano modificando.
Riscrivi partition senza i parametri part1 e part2.
Senza tali parametri sarai costretto a farla realmente ricorsiva.
Se non ci riesci ovviamente vediamo insieme la soluzione.
Puoi scriverla senza l'obbligo che pivot debba rientrare in una delle due liste prodotte.

Ciao
FB
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #2 on: 20-03-2011, 03:29:01 »

la funzione partition e' il piu' chiaro esempio
di come sia difficile evitare di pensare imperativo per chi
lo fa da anni.
Per funzionare funziona. Aggiungiamo anche che e' molto efficiente.
Pero' e' una funzione in cui part1 e part2 giocano il ruolo di due accumulatori
che andiamo man mano modificando.
Riscrivi partition senza i parametri part1 e part2.
Senza tali parametri sarai costretto a farla realmente ricorsiva.
Se non ci riesci ovviamente vediamo insieme la soluzione.
Puoi scriverla senza l'obbligo che pivot debba rientrare in una delle due liste prodotte.

Ciao
FB
Ho cercato di fare quello che ha detto lei e ho modificato un bel po' l'algoritmo... adesso partition2 partiziona "in loco" la lista ls mentre la funzione pivotfind restituisce il primo elemento della lista che non e' in ordine, e se la lista e' ordinata restituisce #f. Di seguito il codice.
Code:
(define (pivotfind ls prec?)
  (cond
    ((or (null? ls)(null? (cdr ls))) #f)
    ((prec? (car ls) (cadr ls)) (pivotfind (cdr ls) prec?))
    (else (car ls))))

(define (partition2 pivot ls prec?)
  (cond
    ((null? ls)
     ls)
    ((prec? (car ls) pivot)
     (cons (car ls) (partition2 pivot (cdr ls) prec?) ))
    (else
     (append (partition2 pivot (cdr ls) prec?) (list (car ls))) )))

(define (quicksortnumber2 ls prec?)
  (let ([pivot (pivotfind ls prec?)])
    (if (equal? pivot #f)
        ls
        (let ([parts (partition2 pivot ls prec?)])
         (quicksortnumber2 parts prec?)) )))



;; Test
(define tosort (list 21 13 40 31 11 34 16 18 62 38 14 51 72 9))
(quicksortnumber2 tosort <)
(quicksortnumber2 tosort >)
P.s. ho dovuto usare la funzione equal? al posto di = in quanto il secondo non riusciva a confrontare i numeri con i booleani perche' a run time scheme e' tipato
« Last Edit: 20-03-2011, 12:59:19 by shiny » Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #3 on: 20-03-2011, 18:15:36 »

Il quicksortnumber2 ha un problemino, ovvero se si usano predicati come <= e >= questo va in "loop" infinito in quanto il pivot in ogni passo ricorsivo sara' sempre il primo elemento... allora mi sono detto perche' non implementare una nuova versione della prima partition che non prende le due liste d'appoggio? (o per meglio dire che maschera questi due parametri).
eccovi il codice della prima partition evoluto
Code:
(define (partition pivot ls prec?)
  (letrec ([partitionrec (lambda (pivot ls p1 p2 prec?)
                      (cond
                        [(null? ls)
                         (list (reverse (cons pivot p1)) (reverse p2))]
                        [(prec? (car ls) pivot)
                         (partitionrec pivot (cdr ls) (cons (car ls) p1) p2 prec?)]
                        [else
                         (partitionrec pivot (cdr ls) p1 (cons (car ls) p2) prec?)] ))])
    (partitionrec pivot ls empty empty prec?)))
Da notare l'uso del letrec senza il quale non si potrebbe valutare la funzione partitionrec 
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #4 on: 20-03-2011, 19:41:41 »

Stiamo sempre li',
la funzione principale non usa argomenti di appoggio, ma fa usa di una funzione
che usa argomenti come fossero variabili che vai man mano modificando.

Provo a scrivere io una versione che, presa una lista ed un pivot,
"divide" la lista in due parti, una di elementi che precedono il pivot,
l'altra di quelli che non precedono.

Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #5 on: 20-03-2011, 20:00:26 »

(define (partition ls pivot prec?)
  (if (null? ls)
      (list empty empty)
      (let ((lsls (partition (cdr ls) pivot prec?)))
        (if (prec? (car ls) pivot)
            (list (cons (car ls)
                           (car lsls))
                  (cadr lsls))
            (list (car lsls)
                  (cons (car ls)
                           (cadr lsls)))))))

Questa versione e' inerentemente ricorsiva.
Ricordatemi domani a questo punto di accennare a cosa
caratterizza una funzione puramente ricorsiva da una intrinsecamente
iterativa.

Ovviamente mi potete fare ora l'osservazione che la tua versione
e' piu' "efficiente", ma qui non ci stiamo ponendo problemi di efficienza.

Si puo' evitare l'uso del let, ma saremmo costretti a richiamare,
e quindi valutare,
due volte  (partition (cdr ls) pivot prec?)

Salutoni
FB
       
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 20-03-2011, 21:33:35 »

prof il problema di essere intrinsecamente iterativa ce l'ha la partition o la partition2 o entrambe? perche' la partition2 divide gli elementi della lista riposizionandoli e senza usare delle liste di appoggio.

P.S. per far funzionare la partition del prof (che ho chiamato partitionp) ho dovuto modificare la funzione quicksortnumber e anche la mia partition... eccovi il codice finale del quicksort che puo' usare per fare le partizioni o la versione partition del prof o quella mia indifferentemente 
Code:
(define (pivotfind ls prec?)
  (cond
    ((or (null? ls)(null? (cdr ls))) #f)
    ((prec? (car ls) (cadr ls)) (pivotfind (cdr ls) prec?))
    (else (car ls))))

;; partition and partitionp function return a list with 2 partitions.
;; The first one contains all the elements prec? of the pivot while the second one contains all the others
(define (partition pivot ls prec?)
  (letrec ([partitionrec (lambda (pivot ls p1 p2 prec?)
                      (cond
                        [(null? ls)
                         (list (reverse p1) (reverse p2))]
                        [(prec? (car ls) pivot)
                         (partitionrec pivot (cdr ls) (cons (car ls) p1) p2 prec?)]
                        [else
                         (partitionrec pivot (cdr ls) p1 (cons (car ls) p2) prec?)] ))])
    (partitionrec pivot ls empty empty prec?)))

(define (partitionp pivot ls prec?)
  (if (null? ls)
      (list empty empty)
      (let ([lsls (partitionp pivot (cdr ls) prec?)])
        (if (prec? (car ls) pivot)
            (list (cons (car ls)(car lsls)) (cadr lsls))
            (list (car lsls) (cons (car ls)(cadr lsls)))))))

;; quicksortnumber function sorts the list in input using the quicksort algorithm
(define (quicksortnumber ls prec?)
  (let ([pivot (pivotfind ls prec?)])
    (if (equal? pivot #f)
        ls
        (let ([parts (partitionp pivot ls prec?)])
          (append (quicksortnumber (car parts) prec?) (quicksortnumber (cadr parts) prec?)) ))))

« Last Edit: 20-03-2011, 22:35:02 by shiny » Logged
TuTToWeB
Apprendista Forumista
**
Offline Offline

Posts: 102


« Reply #7 on: 29-03-2011, 22:14:56 »

Io, personalmente, ho fatto questa versione del quicksort. Ho preso l'algoritmo da wikipedia (ho totalmente scordato come funzionava Cheesy). Ad ogni modo vorrei un giudizione di quanto "imperativo" sia il mio codice

Code:
(define (getElementByIndex ls index)
  (if (>= index (length ls)) #f
      (if (= 0 index) (car ls) (getElementByIndex (cdr ls) (- index 1) )
  )
))

(define (getByPredicate ls predicate val)
  (if (null? ls) empty (if (predicate (car ls) val ) (cons (car ls) (getByPredicate (cdr ls) predicate val))(getByPredicate (cdr ls) predicate val) ))
)

(define (Quicksort ls)
  (realQuicksort ls (getElementByIndex ls (floor (/ (length ls) 2) )))
)

(define (realQuicksort ls piv)
  (if (null? ls) empty (mergeList  (Quicksort (getByPredicate ls < piv) ) (mergeList (list piv) (Quicksort (getByPredicate ls > piv)))))
)

(define (mergeList ls1 ls2)
  (if (empty? ls1) ls2 (if (<= (length ls1) 1) (cons (car ls1) ls2) (cons (car ls1) (mergeList (cdr ls1) ls2) )))
)

Funziona in questo modo
chiamando quicksort in questo modo

(Quicksort (list 8 9 4 1 14 23 45 9))

lui la passa a realQuicksort che non fa altro che divide la lista in base all'elemento centrale (=pivot)
a voi commentare
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #8 on: 30-03-2011, 15:26:43 »

Un primo consiglio per permettere la leggibilita' e' indentare il codice
Code:
(define (getElementByIndex ls index)
    (if (>= index (length ls))
#f
        (if (= 0 index)
(car ls) (getElementByIndex (cdr ls) (- index 1) ))))
inoltre la suddetta funzione fa ricorsione di coda (il prof ha detto di sforzarci a non usarla).
Poi non capisco perche' esegui
Code:
(car ls)
se poi non usi questo valore ma semplicemente lo butti via.
Logged
TuTToWeB
Apprendista Forumista
**
Offline Offline

Posts: 102


« Reply #9 on: 30-03-2011, 17:38:00 »

Un primo consiglio per permettere la leggibilita' e' indentare il codice
Code:
(define (getElementByIndex ls index)
    (if (>= index (length ls))
#f
        (if (= 0 index)
(car ls) (getElementByIndex (cdr ls) (- index 1) ))))
inoltre la suddetta funzione fa ricorsione di coda (il prof ha detto di sforzarci a non usarla).
Poi non capisco perche' esegui
Code:
(car ls)
se poi non usi questo valore ma semplicemente lo butti via.


Non vorrei dire una sciocchezza, io credo che questo sia uno dei casi in cui non si può fare a meno. Potrei (con alta probabilità) sbagliarmi.
Se ho ben capito, in linea generale, una funzione ricorsiva di testa (in soldoni) esegue e poi richiama se stessa, al contrario di quella di coda che richiama se stessa e poi mette in sieme i cocci.
Io credo che qui non si possa fare di meglio poiché qui gli elementi li devi comunque scorrere tutti, fino a N se è necessario.
Poi, se si può fare come di testa, ben venga...così almeno cerco di capire questo concetto su cose fatte da me.
Non ben capito la tua domanda su (car ls). Perdonami, se la funzione si chiama getElementByIndex, quella è la parte che ti restituisce l'i-esimo elemento della lista. Non è che lo butto via, lo restituisco alla funzione chiamante (vd (define Quicksort))

Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #10 on: 30-03-2011, 18:42:44 »

Un primo consiglio per permettere la leggibilita' e' indentare il codice
Code:
(define (getElementByIndex ls index)
    (if (>= index (length ls))
#f
        (if (= 0 index)
(car ls) (getElementByIndex (cdr ls) (- index 1) ))))
inoltre la suddetta funzione fa ricorsione di coda (il prof ha detto di sforzarci a non usarla).
Poi non capisco perche' esegui
Code:
(car ls)
se poi non usi questo valore ma semplicemente lo butti via.


Non vorrei dire una sciocchezza, io credo che questo sia uno dei casi in cui non si può fare a meno. Potrei (con alta probabilità) sbagliarmi.
Se ho ben capito, in linea generale, una funzione ricorsiva di testa (in soldoni) esegue e poi richiama se stessa, al contrario di quella di coda che richiama se stessa e poi mette in sieme i cocci.
Io credo che qui non si possa fare di meglio poiché qui gli elementi li devi comunque scorrere tutti, fino a N se è necessario.
Poi, se si può fare come di testa, ben venga...così almeno cerco di capire questo concetto su cose fatte da me.
Non ben capito la tua domanda su (car ls). Perdonami, se la funzione si chiama getElementByIndex, quella è la parte che ti restituisce l'i-esimo elemento della lista. Non è che lo butto via, lo restituisco alla funzione chiamante (vd (define Quicksort))


si scusami e' che non essendo indentato non avevo capito che quello fosse il valore di ritorno...
per quel che riguarda la funzione penso che come dici te ottenere l'i-esimo elemento non e' possibile se non con ricorsione di coda ma cmq quello a cui mi riferivo io era il fatto di non usare completamente quella funzione (il quicksort puo' prendere come pivot un elemento qualsiasi) e prendere direttamente il primo elemento.
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #11 on: 30-03-2011, 19:01:21 »


Code:
(define (getElementByIndex ls index)
  (if (>= index (length ls)) #f
      (if (= 0 index) (car ls) (getElementByIndex (cdr ls) (- index 1) )
  )
))

(define (getByPredicate ls predicate val)
  (if (null? ls) empty (if (predicate (car ls) val ) (cons (car ls) (getByPredicate (cdr ls) predicate val))(getByPredicate (cdr ls) predicate val) ))
)

(define (Quicksort ls)
  (realQuicksort ls (getElementByIndex ls (floor (/ (length ls) 2) )))
)

(define (realQuicksort ls piv)
  (if (null? ls) empty (mergeList  (Quicksort (getByPredicate ls < piv) ) (mergeList (list piv) (Quicksort (getByPredicate ls > piv)))))
)

(define (mergeList ls1 ls2)
  (if (empty? ls1) ls2 (if (<= (length ls1) 1) (cons (car ls1) ls2) (cons (car ls1) (mergeList (cdr ls1) ls2) )))
)
analizzando il codice piu' che quicksort l'algoritmo e' slowsort in quanto per ottenere una partizione scannerizzi 2 volte la lista alla ricerca prima di quelli minori del pivot e poi di quelli maggiori del pivot quando la stessa cosa si dovrebbe fare in un unica passata ^^

Logged
TuTToWeB
Apprendista Forumista
**
Offline Offline

Posts: 102


« Reply #12 on: 30-03-2011, 20:51:35 »


Code:
(define (getElementByIndex ls index)
  (if (>= index (length ls)) #f
      (if (= 0 index) (car ls) (getElementByIndex (cdr ls) (- index 1) )
  )
))

(define (getByPredicate ls predicate val)
  (if (null? ls) empty (if (predicate (car ls) val ) (cons (car ls) (getByPredicate (cdr ls) predicate val))(getByPredicate (cdr ls) predicate val) ))
)

(define (Quicksort ls)
  (realQuicksort ls (getElementByIndex ls (floor (/ (length ls) 2) )))
)

(define (realQuicksort ls piv)
  (if (null? ls) empty (mergeList  (Quicksort (getByPredicate ls < piv) ) (mergeList (list piv) (Quicksort (getByPredicate ls > piv)))))
)

(define (mergeList ls1 ls2)
  (if (empty? ls1) ls2 (if (<= (length ls1) 1) (cons (car ls1) ls2) (cons (car ls1) (mergeList (cdr ls1) ls2) )))
)
analizzando il codice piu' che quicksort l'algoritmo e' slowsort in quanto per ottenere una partizione scannerizzi 2 volte la lista alla ricerca prima di quelli minori del pivot e poi di quelli maggiori del pivot quando la stessa cosa si dovrebbe fare in un unica passata ^^
Ora mi sono ricordato perché non scrivo più su questo forum da due anni a questa parte!
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #13 on: 30-03-2011, 22:20:58 »

Ora mi sono ricordato perché non scrivo più su questo forum da due anni a questa parte!
O.o??? Non ti piace discutere del tuo codice? Se ti ho ferito scusano ma quello che ho detto e' la pura verità... Te ad ogni passata scannerizzi 2 volte tutti gli elementi per avere le 2 partizioni mentre il quicksort utilizza una sola scansione perché se no il caso medio risulterebbe quadratico 
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #14 on: 31-03-2011, 20:28:45 »

A noi che si faccia in una o due passate poco importa.
Vogliamo imparare a capire la ricorsione.
Una volta capita ci possiamo occupare di efficienza.
Comunque, non e' difficile in questo caso ottenere le due liste
in un'"unica passata" anche se nel nostro caso, essendo ricorsione,
la parola "passata" e' un po' fuorviante.

Salutoni
FB
Logged
Pages: [1]   Go Up
Print
Jump to: