--- 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*)