I will talk about three distinct sorting algorithms. Perhaps, the easiest to implement is the quicksort. In short, it sorts the input by positioning the input around the first element(pivot) and recursively sorts thepartitions. Here is the implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
;;;;;;QUICKSORT;;;;;;;; ;myquicksort: listOfNumbers->listOfNumbers ; Sorts the input by positioning the input around the first element(pivot) and recursively sorts the partitions. ; example: (myquicksort (list 3 2 1 5 4 6))->(list 1 2 3 4 5 6) (define (myquicksort lst) (cond [(empty? lst) empty] [else (append (myquicksort (smaller (rest lst) (first lst))) (list (first lst)) (myquicksort (larger (rest lst) (first lst)))) ])) (check-expect (myquicksort (list 3 2 1 5 4 6)) (list 1 2 3 4 5 6)) ;smaller:listofNumbers, number->listofNumbers ; Selects the smaller elements than pivot from a list ;example:(smaller (list 3 2 7 1 5 8) 5)->(list 3 2 1 5) (define (smaller ls piv) (cond [(empty? ls) empty] [else (cond [(< piv (first ls)) (smaller (rest ls) piv )] [else (cons (first ls) (smaller (rest ls) piv))])])) (check-expect (smaller (list 3 2 7 1 5 8) 5) (list 3 2 1 5)) ;larger:listofNumbers, number->listofNumbers ; Selects the larger elements than pivot from a list ;example:(larger (list 3 2 7 1 5 8) 5)->(list 7 8) (define (larger ls piv) (cond [(empty? ls) empty] [else (cond [(>= piv (first ls)) (larger (rest ls) piv )] [else (cons (first ls) (larger (rest ls) piv))])])) (check-expect (larger (list 3 2 7 1 5 8) 5) (list 7 8)) |

The second algorithm is insertion sort. It sorts the list through successive insertions tocorrect places.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
;;;;;;;;;;INSERTIONSORT;;;;;;;;;;; ; myinsertionsort: listofNumbers->listOfNumbers ; sorts a list through successive insertion to correct places ; example: (myinsertionsort (list 3 2 1 5 4 6))->(list 1 2 3 4 5 6) (define (myinsertionsort lst) (cond [(empty? lst) empty] [else (insert (first lst) (myinsertionsort (rest lst)))])) (check-expect (myinsertionsort (list 3 2 1 5 4 6)) (list 1 2 3 4 5 6)) ;insert: number, listofNumbers->listOfNumbers ; inserts the element to the correct position ; example: (insert 5 (list 1 4 6 8))->(list 1 4 5 6 8) (define (insert x lst) (cond [(empty? lst) (cons x empty)] [else (cond [(> x (first lst)) (cons (first lst) (insert x (rest lst)))] [else (cons x lst)])])) (check-expect (insert 5 (list 1 4 6 8)) (list 1 4 5 6 8)) |