864abae279b7
Sorts
author | Steve Losh <steve@stevelosh.com> |
---|---|
date | Mon, 21 Nov 2016 11:22:22 +0000 |
parents | eee0f45d46b8 |
children | 9f549a9639ca |
branches/tags | (none) |
files | package.lisp sand.asd src/sorting.lisp |
Changes
--- a/package.lisp Sun Nov 20 13:40:53 2016 +0000 +++ b/package.lisp Mon Nov 21 11:22:22 2016 +0000 @@ -46,6 +46,15 @@ :/ :*)) +(defpackage :sand.sorting + (:use + :cl + :losh + :iterate + :cl-arrows + :sand.quickutils + :sand.utils)) + (defpackage :sand.parenscript (:use :cl
--- a/sand.asd Sun Nov 20 13:40:53 2016 +0000 +++ b/sand.asd Mon Nov 21 11:22:22 2016 +0000 @@ -48,6 +48,7 @@ (:file "urn") (:file "random-numbers") (:file "generic-arithmetic") + (:file "sorting") (:file "ascii") (:file "markov") (:file "dijkstra-maps")
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/sorting.lisp Mon Nov 21 11:22:22 2016 +0000 @@ -0,0 +1,36 @@ +(in-package :sand.sorting) + + +;; http://cdn.cs50.net/2015/fall/lectures/3/m/notes3m/notes3m.html + + +(defun bubble-sort (vector) + (iterate + (with size = (length vector)) + (for done = t) + (iterate (for i :from 0 :below (1- size)) + (for j = (1+ i)) + (when (< (aref vector j) (aref vector i)) + (rotatef (aref vector i) + (aref vector j)) + (setf done nil))) + (until done)) + vector) + + +(defun selection-sort (vector) + (iterate + (for target :index-of-vector vector) + (for smallest = (iterate + (for value :in-vector vector :from target :with-index i) + (finding i minimizing value))) + (prl target smallest) + (rotatef (aref vector target) + (aref vector smallest))) + vector) + + + +(defparameter *v* #(1 3 7 0 2 1 4)) +; (selection-sort *v*) +; (bubble-sort *v*)