[tyndur-devel] [PATCH v2] lib: echtes QuickSort
Andreas Freimuth ·
* lib/qsort: GnomeSort durch echten QuickSort-Algorithmus ersetzt. Signed-off-by: Andreas Freimuth <m.nemo at gmx.net> --- 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
Antworten
- [tyndur-devel] [PATCH v2] lib: echtes QuickSort · Kevin Wolf