aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <[email protected]>2017-12-03 01:14:29 +0100
committerErik Liodden <[email protected]>2017-12-03 01:18:18 +0100
commitec0e1f26447678a14815496ae1108b0c94796316 (patch)
tree56d98e07879db1f31314ffe766516a3d8b2bbf4a
parent7ec310160ebbae0215402270fed8cd13cd0f7c27 (diff)
downloadalgdat-ec0e1f26447678a14815496ae1108b0c94796316.tar.gz
add insertion_sort
insertion_sort is decleared as follows: void insertion_sort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); the tricky part here is to get the compar funcion right. two examples: static int str_cmp(const void *s1, const void *s2) { char *c1 = *(char **)s1; char *c2 = *(char **)s2; return strcmp(c1, c2); } static int int_cmp(const void *s1, const void *s2) { int a = *(int *)s1; int b = *(int *)s2; return a - b; }
-rw-r--r--Makefile2
-rw-r--r--sort.c26
-rw-r--r--sort.h15
3 files changed, 35 insertions, 8 deletions
diff --git a/Makefile b/Makefile
index 01b0aa4..67f77f4 100644
--- a/Makefile
+++ b/Makefile
@@ -6,7 +6,7 @@ AR=ar
PROG= oving1
-LIB_OBJS=stack.o queue.o llist.o io.o misc.o
+LIB_OBJS=stack.o queue.o llist.o io.o misc.o sort.o
LIB_FILE=libalgdat.a
LIB_H=structure.h misc.h io.h
LIBS = $(LIB_FILE)
diff --git a/sort.c b/sort.c
new file mode 100644
index 0000000..bb6852a
--- /dev/null
+++ b/sort.c
@@ -0,0 +1,26 @@
+/*
+ * sort.c
+ * implementation of different sorting algorithms
+ *
+ * Erik Liodden
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include "misc.h"
+
+
+void insertion_sort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *))
+{
+ int j, i;
+
+ for (j = 1; j < (int)nel; j++) {
+ for (i = j-1; i >= 0 && compar((char *)base+i*width,
+ (char *)base+j*width) > 0; i--)
+ ;
+ rotate((char *)base + (i+1)*width, (char *)base +j*width,
+ (char *)base +(j+1)*width);
+ }
+}
diff --git a/sort.h b/sort.h
index a292c3c..5c6ea0e 100644
--- a/sort.h
+++ b/sort.h
@@ -2,13 +2,6 @@
* sort.h
* decleration of different sort operations
*
- * Erik Liodden
- */
-
-#ifndef SORT_H
-#define SORT_H
-
-/*
* insertion_sort
* merge_sort
* quick_sort
@@ -16,7 +9,15 @@
* bucket_sort
* counting_sort
* radix_sort
+ *
+ * Erik Liodden
*/
+#ifndef SORT_H
+#define SORT_H
+
+void insertion_sort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *));
+
#endif /* SORT_H */