argcv

codes and stuff

Archive for dezembro 2012

Quicksort em DrRacket

leave a comment »

A seguir uma adaptação (com a adição de definições locais e a consideração de elementos iguais) do algoritmo que pode ser encontrado aqui para o quicksort em DrRacket.

;; maiores : lista-de-números número -> lista-de-números
;; Retorna uma lista composta dos elementos da lista passada
;; como parâmetro que são maiores do que o número dado.
(define (maiores ldn n)
  (cond
    [(empty? ldn) empty]
    [(> (first ldn) n) (cons (first ldn) (maiores (rest ldn) n))]
    [else (maiores (rest ldn) n)]))

;; menores : lista-de-números número -> lista-de-números
;; Retorna uma lista composta dos elementos da lista passada
;; como parâmetro que são menores do que o número dado.
(define (menores ldn n)
  (cond
    [(empty? ldn) empty]
    [(< (first ldn) n) (cons (first ldn) (menores (rest ldn) n))]
    [else (menores (rest ldn) n)]))

;; iguais : lista-de-números número -> lista-de-números
;; Retorna uma lista composta dos elementos da lista passada
;; como parâmetro que são iguais ao o número dado.
(define (iguais ldn n)
  (cond
    [(empty? ldn) empty]
    [(= (first ldn) n) (cons (first ldn) (iguais (rest ldn) n))]
    [else (iguais (rest ldn) n)]))

;; quic-ksort : lista-de-números -> lista-de-números
;; Organiza uma lista de números em ordem crescente.
(define (quick-sort ldn)
  (cond
    [(empty? ldn) empty]
    [else (local 
            ( (define esq (menores ldn (first ldn)))
              (define cen (iguais ldn (first ldn)))
              (define dir (maiores ldn (first ldn))) )
            (append (quick-sort esq) cen (quick-sort dir)))]))

;; Testes
(quick-sort (list -4 -4 -2 -5 2 6 3 -2 -7))
(quick-sort (list 9 8 7 6 5 4 3 2 1 0 1 1))

Coloridinho: http://pastebin.com/pMLwnMhe

Anúncios

Written by rntreis

dezembro 16, 2012 at 11:15 am

Publicado em programação