#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
// Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
//////////////
+#include <mathematics/chaos.h>
+
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>
}
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.
};
/*!
* 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.