aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <[email protected]>2017-12-04 00:43:49 +0100
committerErik Liodden <[email protected]>2017-12-04 00:43:49 +0100
commit13eb9ceb1168010e1e329bc049f469b46540326b (patch)
tree7b95b5d86bc0753255abc96a13ae3cc1b4ccb7e8
parentc14d266eb7b1f19aebcc20891f86c84f5105d1b4 (diff)
downloadalgdat-13eb9ceb1168010e1e329bc049f469b46540326b.tar.gz
add quick_sort.
same prototype as the library function qsort.
-rw-r--r--sort.c35
-rw-r--r--sort.h2
2 files changed, 37 insertions, 0 deletions
diff --git a/sort.c b/sort.c
index 7476dd4..f3fb570 100644
--- a/sort.c
+++ b/sort.c
@@ -6,6 +6,7 @@
*/
#include <stddef.h>
+#include <string.h>
#include "misc.h"
@@ -22,3 +23,37 @@ void insertion_sort(void *base, size_t nel, size_t width,
(char *)base +(j+1)*width);
}
}
+
+static int partition(void *base, int p, int r, size_t width,
+ int (*compar)(const void *, const void *))
+{
+ int i, j;
+ void *x = allocate(width);
+ memcpy(x, (char *)base + r*width, width);
+ i = p-1;
+ for (j = p; j <= r-1; j++) {
+ if (compar((char *)base + j*width, x) <= 0) {
+ i = i+1;
+ swap((char *)base +i*width, (char *)base +j*width, width);
+ }
+ }
+ swap((char *)base + (i+1)*width, (char *)base + r*width, width);
+ return i+1;
+}
+
+static void q_sort(void *base, int p, int r, size_t width,
+ int (*compar)(const void *, const void *))
+{
+ int q;
+ if (p < r) {
+ q = partition(base, p, r, width, compar);
+ q_sort(base, p, q-1, width, compar);
+ q_sort(base, q+1, r, width, compar);
+ }
+}
+
+void quick_sort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *))
+{
+ q_sort(base, 0, (int)nel-1, width, compar);
+}
diff --git a/sort.h b/sort.h
index 3106162..eba956f 100644
--- a/sort.h
+++ b/sort.h
@@ -20,6 +20,8 @@ void insertion_sort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
void heap_sort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
+void quick_sort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *));
#endif /* SORT_H */