quicksort.rkt

#lang racket

;; Can make these more slick w/ higher-order functions
(define (elements< l n)
  (match l
    ['() '()]
    [`(,first ,rest ...) #:when (< first n)
      (cons first (elements< rest n))]
    [else (elements< (rest l) n)]))

(define (elements> l n)
  (match l
    ['() '()]
    [`(,first ,rest ...) #:when (> first n)
      (cons first (elements> rest n))]
    [else (elements> (rest l) n)]))

(define (elements= l n)
  (match l
    ['() '()]
    [`(,first ,rest ...) #:when (= first n)
      (cons first (elements= rest n))]
    [else (elements= (rest l) n)]))

(define (quicksort l)
  (if (empty? l)
      '()
      (let* ([pivot (first l)]
             [pivot-list (elements= l pivot)]
             [restl (remove pivot l)]
             [elements-lt (elements< restl pivot)]
             [elements-gt (elements> restl pivot)])
        (append
         (quicksort elements-lt)
         pivot-list
         (quicksort elements-gt)))))

(define (random-list i n)
  (if (= i 0)
      '()
      (cons (random 0 n) (random-list (- i 1) n))))

(define (counterexamples num-tries list-size max-n)
  (define (loop i l)
    (if (= i 0)
        l
        (let* ([lst (random-list list-size max-n)]
               [sorted-via-sort (sort lst <)]
               [sorted-via-qsort (quicksort lst)])
          (if (equal? sorted-via-sort sorted-via-qsort)
              (loop (- i 1) l)
              (loop (- i 1) (cons lst l))))))
  (loop num-tries '()))
          
;(counterexamples 300 300 300)