X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=nucleus%2Flibrary%2Falgorithms%2Fsorts.h;h=c6e21abedc66ec69992016668e7e1ec51685db14;hb=9a99a7a46834665ebf5cab081fa7fe3cc2a8aa11;hp=9a390cb93a08c87ce5d8b6ff9851c9dae1bb00ba;hpb=0cc8bcdf18d075ad1297a054e571570e75624e84;p=feisty_meow.git

diff --git a/nucleus/library/algorithms/sorts.h b/nucleus/library/algorithms/sorts.h
index 9a390cb9..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,8 +16,7 @@
 // Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
 //////////////
 
-#include <stdio.h>
-//temp!
+#include <mathematics/chaos.h>
 
 namespace algorithms {
 
@@ -47,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>
@@ -95,8 +94,7 @@ namespace algorithms {
 	 * merges two sorted arrays into a single sorted array.
 	 */
 	template<class type>
-	basis::array<type> merge(basis::array<type> &first, basis::array<type> &second,
-	  bool reverse)
+	basis::array<type> merge(basis::array<type> &first, basis::array<type> &second, bool reverse)
 	{
 		basis::array<type> to_return;
 		// operate until we've consumed both of the arrays.
@@ -108,8 +106,7 @@ namespace algorithms {
 			} else if (second.length() <= 0) {
 				to_return += first[0];
 				first.zap(0, 0);
-			} else if ( (!reverse && (first[0] <= second[0]))
-					|| (reverse && (first[0] >= second[0]))) {
+			} else if ((!reverse && (first[0] <= second[0])) || (reverse && (first[0] >= second[0]))) {
 				// the first list has a better value to add next.
 				to_return += first[0];
 				first.zap(0, 0);
@@ -269,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.
 	};
 
 	/*!
@@ -286,13 +283,8 @@ namespace algorithms {
 		// reverse the sense of "reverse", since our algorithm expects a normal heap (with largest on top).
 		heap<type> hap(v, n, !reverse);
 
-		//temp
-//		printf("hey after heaping: %s\n", dump_list(v, n).s());
-
 		int end = n - 1;
 		while (end > 0) {
-
-//printf("moving value %d\n", (int)v[0]);
 			// a[0] is the root and largest value for a normal heap. The swap moves it to the real end of the list and takes it out of consideration.
 			hap.swap_values(end, 0);
 			// reduce the heap size by 1.
@@ -304,23 +296,48 @@ namespace algorithms {
 
 //////////////
 
+	//! swaps the values in the array stored at positions a and b.
 	template<class type>
-	void partition(type v[], int start, int end)
+	void swap_values(type array[], int a, int b)
 	{
+		type temp = array[a];
+		array[a] = array[b];
+		array[b] = temp;
+	}
 
+	// hoare's partition implementation.
+	template<class type>
+	int partition(type a[], int start, int end, bool reverse)
+	{
+//		printf("before partition: %s\n", dump_list(a + start, end - start + 1).s());
+		int pivot = a[start];
+		int i = start - 1;
+		int j = end + 1;
+		while (true) {
+			do {
+				i++;
+			} while ((!reverse && (a[i] < pivot)) || (reverse && (a[i] > pivot)));
+			do {
+				j--;
+			} while ((!reverse && (a[j] > pivot)) || (reverse && (a[j] < pivot)));
+
+			if (i >= j) {
+//				printf("after partition: %s\n", dump_list(a + start, end - start + 1).s());
+				return j;
+			}
+			swap_values(a, i, j);
+		}
 	}
 
-//! the recursive version of quick sort that does the work for our convenience method.
+	//! the recursive version of quick sort that does the work for our convenience method.
 	template<class type>
-	void inner_quick_sort(type v[], int n, int start, int end, bool reverse = false)
+	void inner_quick_sort(type v[], int start, int end, bool reverse)
 	{
-		if (start >= end) {
-			// nothing to see here.
-		} else {
+		if (start < end) {
 			// figure out where to pivot, and sort both halves around the pivot index.
-			int pivot = partition(v, start, end);
-			quicksort(v, start, pivot - 1);
-			quicksort(v, pivot + 1, end);
+			int pivot = partition(v, start, end, reverse);
+			inner_quick_sort(v, start, pivot, reverse);
+			inner_quick_sort(v, pivot + 1, end, reverse);
 		}
 	}
 
@@ -330,10 +347,25 @@ 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, n, 0, n - 1, reverse);
+		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.