[tyndur-devel] [PATCH v2] 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 |   72 ++++++++++++++++++++++++++++++++++++++++---------------
 1 files changed, 52 insertions(+), 20 deletions(-)

diff --git a/src/lib/sort.c b/src/lib/sort.c
index 8717c96..e457db4 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) {
+    if(a == b) {
         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++;
+    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