Added qsort, stolen from libnix.

1 files changed, 51 insertions, 0 deletions

diff --git a/libc/src/qsort.c b/libc/src/qsort.c
new file mode 100755
index 0000000..eeb038b
--- /dev/null
+++ b/libc/src/qsort.c
@@ -0,0 +1,51 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+/* sample compar function: int cmp(void *a,void *b){ return *(int *)a-*(int *)b; } */
+
+/* This qsort function does a little trick:
+ * To reduce stackspace it iterates the larger interval instead of doing
+ * the recursion on both intervals. 
+ * So stackspace is limited to 32*stack_for_1_iteration = 
+ * 32*4*(4 arguments+1 returnaddress+11 stored registers) = 2048 Bytes,
+ * which is small enough for everybodys use.
+ * (And this is the worst case if you own 4GB and sort an array of chars.)
+ * Sparing the function calling overhead does improve performance, too.
+ */
+
+void qsort
+(void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *))
+{ char *base2=(char *)base;
+  size_t i,a,b,c;
+  while(nmemb>1)
+  { a=0;
+    b=nmemb-1;
+    c=(a+b)/2; /* Middle element */
+    for(;;)
+    { while((*compar)(&base2[size*c],&base2[size*a])>0) 
+        a++; /* Look for one >= middle */
+      while((*compar)(&base2[size*c],&base2[size*b])<0) 
+        b--; /* Look for one <= middle */
+      if(a>=b)
+        break; /* We found no pair */
+      for(i=0;i<size;i++) /* swap them */
+      { char tmp=base2[size*a+i];
+        base2[size*a+i]=base2[size*b+i];
+        base2[size*b+i]=tmp; }
+      if(c==a) /* Keep track of middle element */
+        c=b;
+      else if(c==b)
+        c=a;
+      a++; /* These two are already sorted */
+      b--;
+    } /* a points to first element of right intervall now (b to last of left) */
+    b++;
+    if(b<nmemb-b) /* do recursion on smaller intervall and iteration on larger one */
+    { qsort(base2,b,size,compar);
+      base2=&base2[size*b];
+      nmemb=nmemb-b; }
+    else
+    { qsort(&base2[size*b],nmemb-b,size,compar);
+      nmemb=b; }
+  }
+}