864abae279b7

Sorts
[view raw] [browse files]
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*)