plugging in new approach for testing

[feisty_meow.git] / nucleus / library / algorithms / sorts.h

diff --git a/nucleus/library/algorithms/sorts.h b/nucleus/library/algorithms/sorts.h
index 55f959b0f8dad2a70a602b03185803db320b8beb..0b7cfc4bd9da20a2ea99656b17552ae063dc72f4 100644 (file)
--- 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,10 @@
 // Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
 //////////////
 
+#include <mathematics/chaos.h>
+
+#include <system_helper.h>
+
 namespace algorithms {
 
        /*
@@ -44,7 +48,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 +268,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 +349,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.