replaced bubble sort with quick sort

added distance(a, b) functions

svn-id: r46638

1 files changed, 63 insertions, 37 deletions

diff --git a/common/algorithm.h b/common/algorithm.h
index 01042536f6..1860e7a070 100644
--- a/common/algorithm.h
+++ b/common/algorithm.h
@@ -26,6 +26,7 @@
 #define COMMON_ALGORITHM_H
 
 #include "common/scummsys.h"
+#include "common/func.h"
 
 namespace Common {
 
@@ -145,57 +146,82 @@ Op for_each(In first, In last, Op f) {
 	return f;
 }
 
-/**
- * Simple sort function, modeled after std::sort.
- * Use it like this: sort(container.begin(), container.end()).
- * Also works on plain old i.e. int arrays etc. For comperance
- * operator < is used.
- */
-template<class T>
-void sort(T first, T last) {
-	if (first == last)
-		return;
+template<typename T>
+unsigned distance(T* first, T* last) {
+	return last - first;
+}
+
+template<typename T>
+unsigned distance(T first, T last) {
+	unsigned n = 0;
+	while(first != last) {
+		++n;
+		++first;
+	}
+	return n;
+}
+
+template<typename T>
+T* _sort_choose_pivot(T* first, T* last) {
+	return first + distance(first, last) / 2;
+}
+
+template<typename T>
+T _sort_choose_pivot(T first, T last) {
+	unsigned n = distance(first, last);
+	n /= 2;
+	while(n--) 
+		++first;
+	return first;
+}
 
-	// Simple selection sort
-	T i(first);
-	for (; i != last; ++i) {
-		T minElem(i);
-		T j(i);
-		++j;
-		for (; j != last; ++j)
-			if (*j < *minElem)
-				minElem = j;
-		if (minElem != i)
-			SWAP(*minElem, *i);
+template<typename T, class StrictWeakOrdering>
+T _sort_partition(T first, T last, T pivot, StrictWeakOrdering &comp) {
+	--last;
+	SWAP(*pivot, *last);
+
+	T sorted;
+	for(sorted = first; first != last; ++first) {
+		if (!comp(*last, *first)) {
+			if (first != sorted)
+				SWAP(*first, *sorted);
+			++sorted;
+		}
 	}
+
+	SWAP(*last, *sorted);
+	return sorted;
 }
 
 /**
  * Simple sort function, modeled after std::sort.
  * It compares data with the given comparator object comp.
- *
- * Note: Using this with: Common::Less from common/func.h
- * will give the same results as the plain sort function.
  */
-template<class T, class StrictWeakOrdering>
+
+template<typename T, class StrictWeakOrdering>
 void sort(T first, T last, StrictWeakOrdering comp) {
 	if (first == last)
 		return;
 
-	// Simple selection sort
-	T i(first);
-	for (; i != last; ++i) {
-		T minElem(i);
-		T j(i);
-		++j;
-		for (; j != last; ++j)
-			if (comp(*j, *minElem))
-				minElem = j;
-		if (minElem != i)
-			SWAP(*minElem, *i);
-	}
+	T pivot = _sort_choose_pivot(first, last);
+	pivot = _sort_partition(first, last, pivot, comp);
+	sort<T, StrictWeakOrdering>(first, pivot, comp);
+	sort<T, StrictWeakOrdering>(++pivot, last, comp);
 }
 
+/**
+ * Simple sort function, modeled after std::sort.
+ * Use it like this: sort(container.begin(), container.end()).
+ */
+
+template<typename T>
+void sort(T* first, T* last) {
+	sort(first, last, Common::Less<T>());
+}
+
+///\todo add value_type to all iterators and add default sort variant with Common::Less<T::value_type>()
+
+
 } // End of namespace Common
 #endif