X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=nucleus%2Flibrary%2Falgorithms%2Fsorts.h;h=c6e21abedc66ec69992016668e7e1ec51685db14;hb=0b6e422c239b59810f7eb2b33abff3c0fe9b720f;hp=55f959b0f8dad2a70a602b03185803db320b8beb;hpb=73eafb33f2098bbd06ddbacab14feda5d0508c22;p=feisty_meow.git

diff --git a/nucleus/library/algorithms/sorts.h b/nucleus/library/algorithms/sorts.h
index 55f959b0..c6e21abe 100644
--- a/nucleus/library/algorithms/sorts.h
+++ b/nucleus/library/algorithms/sorts.h
@@ -2,7 +2,7 @@
 #define ASSORTED_SORTS_GROUP
 
 //////////////
-// Name   : shell_sort
+// Name   : sorts
 // Author : Chris Koeritz
 //////////////
 // Copyright (c) 1991-$now By Author.  This program is free software; you can
@@ -16,6 +16,8 @@
 // Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
 //////////////
 
+#include <mathematics/chaos.h>
+
 namespace algorithms {
 
 	/*
@@ -44,7 +46,7 @@ namespace algorithms {
 	/*!
 	 * Sorts a C array of the "type" with "n" elements.
 	 * Operates on the original array.
-	 * Performs in O(n log(n)) time.
+	 * Performs within O(n^2) time (depending on the gap size used).
 	 * Algorithm is based on Kernighan and Ritchie's "The C Programming Language".
 	 */
 	template<class type>
@@ -264,9 +266,9 @@ namespace algorithms {
 		}
 
 	private:
-		bool _reverse = false;  // is the sorting in reverse?
-		int _total = 0;
-		int *_heapspace = NULL_POINTER;
+		bool _reverse;  // is the sorting in reverse?
+		int _total;  // how many total elements are there?
+		int *_heapspace;  // track a pointer to the array.
 	};
 
 	/*!
@@ -345,12 +347,27 @@ namespace algorithms {
 	 * operates in O(n log(n)) time on average, worst case O(n^2).
 	 * sorts the original array.
 	 */
-	template<class type>
+	template <class type>
 	void quick_sort(type v[], int n, bool reverse = false)
 	{
 		inner_quick_sort(v, 0, n - 1, reverse);
 	}
 
+	//////////////
+
+	//! handy method for randomizing the order of a list.  not strictly a sorting function...
+	template <class type>
+	void randomize_list(type v[], int n)
+	{
+		mathematics::chaos randomizer;
+		for (int i = 0; i < n; i++) {
+			// we will swap with any element that is not prior to the current index; thus we allow
+			// swapping the element with itself and later, but not with anything earlier.
+			int swap_index = randomizer.inclusive(i, n - 1);
+			swap_values(v, i, swap_index);
+		}
+	}
+
 }  // namespace.
 
 #endif // outer guard.