[tyndur-devel] [PATCH] lib: echtes QuickSort

[Andreas Freimuth <m.nemo@xxxxxxx>]

* lib/qsort: GnomeSort durch echten QuickSort-Algorithmus ersetzt.

Signed-off-by: Andreas Freimuth <m.nemo@xxxxxxx>
---
 src/lib/sort.c |   82 +++++++++++++++++++++++++++++++++++++++-----------------
 1 files changed, 57 insertions(+), 25 deletions(-)

diff --git a/src/lib/sort.c b/src/lib/sort.c
index 8717c96..83ff7f5 100644
--- a/src/lib/sort.c
+++ b/src/lib/sort.c
@@ -29,30 +29,62 @@
 #include <stdlib.h>
 #include <string.h>
 
-void qsort(void *base, size_t num, size_t size, int (*comparator)(const void *, const void *))
+static void swap(void* a, void* b, size_t size)
 {
-    //FIXME
-    //Die Funktion heißt Qsort... Gnomesort tuts zwar meistens auch, ist aber
-    //nicht Sinn der Sache, außerdem bin ich grad zu müde für sowas :p
-    unsigned char _tmp[size];
-    void* tmp = _tmp;
-    int i = 0;
-
-    if (num == 0) {
-        return;
-    }
-
-    while (i < (num - 1)) {
-        if (comparator(base + i * size, base + (i + 1) * size) > 0) {
-            memcpy(tmp, base + i * size, size);
-            memcpy(base + i * size, base + (i + 1) * size, size);
-            memcpy(base + (i + 1) * size, tmp, size);
-            
-            if (i > 0) {
-                i--;
-            }
-        } else {
-            i++;
-        }
-    }
+	if(a == b) {
+		return;
+	}
+
+	char temp[size];
+	memcpy(temp, a, size);
+	memcpy(a, b, size);
+	memcpy(b, temp, size);
 }
+
+void qsort(void* base, size_t num, size_t size, int (*comparator)(const void*, const void*))
+{
+	if(num < 2) {
+		return;
+	}
+
+	size_t left = 1, right = num - 1;
+
+	/*
+	 * Als Pivot-Element p ist das Element mit Index 0 gewählt. Das Array wird
+	 * grob vorsortiert indem alles was kleiner p ist nach links und alles was
+	 * größer oder gleich p ist nach rechts gebracht wird.
+	 */
+	while(left <= right) {
+		while((left <= right) && (comparator(base, base + left * size) > 0)) {
+			++left;
+		}
+
+		while((left < right) && (comparator(base, base + right * size) <= 0)) {
+			--right;
+		}
+
+		if(left >= right) {
+			break;
+		}
+
+		swap(base + left * size, base + right * size, size);
+		++left; --right;
+	}
+
+	/*
+	 * Hier angekommen zeigt left auf das erste Element, welches nicht kleiner
+	 * ist als das Pivot-Element. left soll aber auf das letzte Element zeigen
+	 * das kleiner ist als das Pivot-Element. right könnte auf dieses zeigen,
+	 * soll aber auf das erste nicht kleiner Element zeigen.
+	 */
+	right = left--;
+
+	/* Pivot-Element einsortieren */
+	swap(base, base + left * size, size);
+
+	/* Linke Seite sortieren. */
+	qsort(base, left, size, comparator);
+	/* Rechte Seite sortieren. */
+	qsort(base + right * size, num - right, size, comparator);
+}
+
-- 
1.7.6.2