[genius] Thu Jul 14 16:34:40 2011 Jiri (George) Lebl <jirka 5z com>

[George Lebl <jirka src gnome org>]

commit 85f3a7d0a79632db854c0cbdaafa355a70d46180
Author: Jiri (George) Lebl <jirka 5z com>
Date:   Thu Jul 14 16:34:47 2011 -0700

    Thu Jul 14 16:34:40 2011  Jiri (George) Lebl <jirka 5z com>
    
    	* lib/linear_algebra/misc.gel: Optimize SortVector (use quicksort
    	  for longer vectors)

 ChangeLog                   |    5 +++
 lib/linear_algebra/misc.gel |   62 ++++++++++++++++++++++++++++++++++---------
 2 files changed, 54 insertions(+), 13 deletions(-)
---
diff --git a/ChangeLog b/ChangeLog
index f1ceb8b..c9baa58 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+Thu Jul 14 16:34:40 2011  Jiri (George) Lebl <jirka 5z com>
+
+	* lib/linear_algebra/misc.gel: Optimize SortVector (use quicksort
+	  for longer vectors)
+
 Tue Jul 12 23:16:59 2011  Jiri (George) Lebl <jirka 5z com>
 
 	* src/eval.c, src/structs.h, src/parse.y, src/lexer.l, src/calc.c,
diff --git a/lib/linear_algebra/misc.gel b/lib/linear_algebra/misc.gel
index 6104ebf..cea8eb0 100644
--- a/lib/linear_algebra/misc.gel
+++ b/lib/linear_algebra/misc.gel
@@ -230,19 +230,55 @@ function SortVector(v) = (
 	if IsNull(v) then return null
 	else if not IsVector(v) then
 		(error("SortVector: argument not a vector");bailout);
-	# FIXME: really bad bubble sort
-	j = 1;
-	do (
-		sorted = true;
-		for i = 1 to elements(v)-j do (
-			if v@(i)>v@(i+1) then (
-				v@(i) swapwith v@(i+1);
-				sorted = false
-			)
-		);
-		j=j+1
-	) while not sorted;
-	v
+
+	# cross between bubble and quicksort.  Bubble sort is faster in GEL
+	# for short arrays
+
+	function bubble(v) = (
+		j = elements(v)-1;
+		do (
+			unsorted = false;
+			for i = 1 to j do (
+				if v@(i) > v@(i+1) then (
+					v@(i) swapwith v@(i+1);
+					unsorted = true
+				)
+			);
+			increment j by -1
+		) while unsorted;
+		v
+	);
+	function quicksort(v) = (
+		if elements(v) <= 9 then
+			bubble(v)
+		else (
+			pe = floor(elements(v)/2);
+			piv = v@(pe);
+			less = more = .;
+			k = 1;
+			j = 1;
+			for i=1 to pe-1 do (
+				if v@(i) <= piv then (
+					less@(k) = v@(i);
+					increment k
+				) else (
+					more@(j) = v@(i);
+					increment j
+				)
+			);
+			for i=pe+1 to elements(v) do (
+				if v@(i) <= piv then (
+					less@(k) = v@(i);
+					increment k
+				) else (
+					more@(j) = v@(i);
+					increment j
+				)
+			);
+			[quicksort(less), piv, quicksort(more)]
+		)
+	);
+	quicksort(v)
 );
 
 SetHelp("ReverseVector","matrix","Reverse elements in a vector");